31001：无权图最短路

题目

在 30012 的 IntGraph 上求从 source 到 target 的无权最短距离；不可达时返回 SIZE_MAX。

解析

无权边的每次移动代价相同，BFS 按距离层次访问顶点。顶点第一次入队时得到的距离就是最短距离；访问标记在入队时设置，重复边不会重复入队。临时距离数组和队列准备完成后才写出结果。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct GraphEdge GraphEdge;
typedef struct IntGraph IntGraph;

struct GraphEdge {
    size_t to;
    GraphEdge *next;
};

typedef struct {
    GraphEdge *head;
    GraphEdge *tail;
} Adjacency;

struct IntGraph {
    Adjacency *adj;
    size_t vertex_count;
    bool directed;
};

bool int_graph_shortest_distance(
    const IntGraph *graph,
    size_t source,
    size_t target,
    size_t *out_distance
) {
    if (graph == NULL || out_distance == NULL ||
        source >= graph->vertex_count ||
        target >= graph->vertex_count ||
        graph->vertex_count > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    size_t *distance = malloc(
        graph->vertex_count * sizeof *distance
    );
    size_t *queue = malloc(
        graph->vertex_count * sizeof *queue
    );
    if (distance == NULL || queue == NULL) {
        free(distance);
        free(queue);
        return false;
    }
    for (size_t i = 0; i < graph->vertex_count; ++i) {
        distance[i] = SIZE_MAX;
    }

    size_t front = 0;
    size_t back = 0;
    distance[source] = 0;
    queue[back++] = source;
    while (front < back && distance[target] == SIZE_MAX) {
        size_t vertex = queue[front++];
        for (GraphEdge *edge = graph->adj[vertex].head;
             edge != NULL;
             edge = edge->next) {
            if (edge->to >= graph->vertex_count) {
                free(distance);
                free(queue);
                return false;
            }
            if (distance[edge->to] == SIZE_MAX) {
                if (distance[vertex] == SIZE_MAX - 1) {
                    free(distance);
                    free(queue);
                    return false;
                }
                distance[edge->to] = distance[vertex] + 1;
                queue[back++] = edge->to;
            }
        }
    }
    *out_distance = distance[target];
    free(distance);
    free(queue);
    return true;
}

每个顶点只入队一次，每条邻接边只检查一次，时间复杂度为 $O(V+E)$，额外空间为 $O(V)$。