BFS 求无权图最短路径

2026 大纲 五（四）图的基本应用 2. 最短路径 · 无权图（遍历本身见《BFS》）。

层号本来就是距离，只是没记下来

BFS 那一篇已经把最要紧的事实说完了：BFS 按"距源点由近到远"访问顶点，第 $k$ 层的顶点距源点恰好 $k$ 条边。

所以求最短路径根本不需要新算法——只要在遍历时顺手把层号记下来就行。这个改造的开销是零：每个顶点一次 $O(1)$ 的赋值，复杂度与单纯遍历完全相同。

改造只加两个数组：

• d[v]：源点到 $v$ 的最短距离，初值 $-1$。
• path[v]：最短路径上 $v$ 的前一个顶点，初值 $-1$。

为什么记前驱而不是整条路径？ 因为记整条路径要为每个顶点存一个变长序列，空间 $O(n^2)$。而每个顶点在最短路径树上只有一个父亲，一个 $O(n)$ 的父指针数组顺着往回走就能还原出整条路。换句话说，path[] 存的就是 BFS 生成树的父指针。

先动手看一眼

加载可视化中...

盯 d[] 那一行：它是一层填满才轮到下一层的。这个现象后面会被用来证明"首次到达即最短"。

实现与路径还原

int d[MAX_V];        // 源点到各顶点的最短距离，-1 表示未访问 / 不可达
int path[MAX_V];     // 最短路径上各顶点的前驱，-1 表示无前驱

void BFS_ShortestPath(int s, int n) {
    for (int i = 0; i < n; i++) { d[i] = -1; path[i] = -1; }
    Queue Q; InitQueue(&Q);
    d[s] = 0;                   // 置 d[s] 就等于把 s 标记成已访问
    EnQueue(&Q, s);

    while (!IsEmpty(&Q)) {
        int u;
        DeQueue(&Q, &u);
        for (int v = FirstNeighbor(u); v >= 0; v = NextNeighbor(u, v))
            if (d[v] == -1) {       // 未访问 → 这是第一次到达 v
                d[v] = d[u] + 1;    // 距离 = 前驱距离 + 1
                path[v] = u;
                EnQueue(&Q, v);     // 赋值与入队同时完成
            }
    }
}

三处值得单独说：

visited[] 不见了。 因为 d[v] != -1 已经完整承担了"已访问"的语义——d[v] 是在入队的同一时刻赋值的。多留一个 visited[] 不算错，只是冗余。

赋值必须与入队同时。 把 d[v] 的赋值挪到出队之后，d[v] == -1 就不再等价于"未访问"，同一个顶点会被重复入队、距离被覆盖成错的。这就是 BFS 的"入队即置位"纪律，只是这里置的是 d[]。

d[v] == -1 有两种读法。 运行中它表示"还没访问到"，运行结束后它表示"不可达"——同一个事实在两个时刻的两种读法。初值取 $-1$ 而不是 0，是因为 0 已经被源点占用了（$d[s]=0$）。

还原路径时沿 path[] 往回走，得到的是逆序，借助栈翻正：

void PrintPath(int s, int t) {
    if (d[t] == -1) { printf("不可达\n"); return; }
    int stack[MAX_V], top = -1;
    for (int v = t; v != -1; v = path[v])
        stack[++top] = v;
    while (top >= 0) printf("%d ", stack[top--]);
    printf("\n");
}

循环终止条件 v != -1 靠的是 path[s] == -1（源点没有前驱）这一初始化。若把 path[s] 初始化成 $s$ 自己，条件必须相应改成 v != s 并在循环外补上源点，否则死循环——两种写法各自自洽，不能混用。

path[] 能不能省？只求距离可以省；问"写出最短路径"就不能。$d[]$ 回答"多少"、$path[]$ 回答"怎么走"，两者不能互相导出——从 $d[]$ 反推路径还得再做一次 $O(n+e)$ 的搜索。

顺带一条结论：最短距离唯一，但最短路径不唯一。path[v] 记的是实际首次发现 $v$ 的那个顶点，取决于邻接表里边的次序；换一份邻接表，path[] 可能整个变一份，而 d[] 一格都不会变。

什么时候能用它，什么时候不能

这是这一节唯一真正需要判断的事，而且判据只有一句话：

🔴 只要"每走一步付出的代价相同"，BFS 就适用。

于是分成三种情形：

能用（一）：无权图。 每条边都是一步，天然满足。

能用（二）：所有边权都相等的带权图。 这一种最容易被漏掉。每条边权都是 $c$ 时，最小权和 $=c\times$ 最少边数，所以照跑 BFS，最后把 $d[]$ 整体乘以 $c$ 就行，完全不需要 Dijkstra。真题在这里出过一道判断题：给一个"各边权均为 1 的无向连通图"，问 Prim / Kruskal / BFS 里哪些一定能求出某顶点到其余各顶点的最短路径——答案只有 BFS。

⚠️ 那道题的关键不在 BFS 行不行，而在为什么 Prim 和 Kruskal 不行。它们求的是最小生成树，最小化的是全树边权之和；最短路径树最小化的是源点到每个顶点各自的距离。目标不一样，结果自然可以不一样：四个顶点连成等权环，MST 去掉一条边变成一条链，链上两端的距离是 3，而原图里它们直接相邻、距离是 1。

不能用：边权不全相等。 反例只要三个顶点：$0\to 1$ 权 100、$0\to 2$ 权 1、$2\to 1$ 权 1。BFS 认为 $0\to 1$ 最短（只用 1 条边），但 $0\to 2\to 1$ 的代价只有 2。"边最少"和"权和最小"指向了不同的路径，这时必须换 Dijkstra。

反过来看这件事会更清楚：Dijkstra 就是把 BFS 的普通队列换成"按当前距离取最小"的优先队列。所有边权相等时，"按距离取最小"和"按入队先后取"给出同一个顺序，两个算法退化成同一个。

三种最短路径算法怎么选

选型的第一问永远是"图有没有权、权是不是全相等"，第二问才是"单源还是全源"：

算法	适用图	求什么	时间	判别依据
BFS	无权 / 边权全相等	单源	$O(n+e)$	每条边代价是否一样，是则用它，最快
Dijkstra	带权，权非负	单源	$O(n^2)$ 或 $O(e\log n)$	有正权、只要一个源点
Floyd	带权，允许负权边，不允许负权回路	所有顶点对	$O(n^3)$	要全部点对，或存在负权边

六顶点无权图的逐步走查（想手动填 d 表与 path 表就展开）

$E=\{(0,1),(0,2),(1,3),(1,4),(2,4),(4,5)\}$：

    0 --- 1 --- 3
    |     |
    2 --- 4 --- 5

邻接表按编号升序：$0:1,21:0,3,42:0,43:14:1,2,55:4$

步骤	出队顶点 $u$	检查 $u$ 的邻居	新发现	$d$ 更新	$path$ 更新	队列（出队后）
初始	—	—	0	$d[0]=0$	—
1	0	1, 2	1, 2	$d[1]=1,d[2]=1$	$path[1]=0,path[2]=0$
2	1	0(已), 3, 4	3, 4	$d[3]=2,d[4]=2$	$path[3]=1,path[4]=1$
3	2	0(已), 4(已)	—	—	—
4	3	1(已)	—	—	—
5	4	1(已), 2(已), 5	5	$d[5]=3$	$path[5]=4$
6	5	4(已)	—	—	—

最终结果：

顶点	0	1	2	3	4	5
$d$	0	1	1	2	2	3
$path$	−1	0	0	1	1	4

还原 $0\to 5$：$path[5]=4\to path[4]=1\to path[1]=0\to path[0]=-1$ 停。压栈序列 $5,4,1,0$，弹栈得 $0\to 1\to 4\to 5$，长度 3 $=d[5]$ ✓。

注意第 3 步：顶点 2 检查到邻居 4 时，4 已在第 2 步被 1 发现，所以跳过、不更新。若这里改成"更新"，$d[4]$ 会被写成 $d[2]+1=2$——数值上碰巧还是 2，但 $path[4]$ 会变成 2，路径变成 $0\to 2\to 4\to 5$。这条路径长度同样是 3，同样是一条最短路径——说明最短路径可能不唯一，而 path[] 只记录了 BFS 实际走出的那一条。

"首次到达即最短"的证明（想弄清它依赖队列的哪条性质就展开）

命题：BFS 结束后，对任意可达顶点 $v$，d[v] 等于源点 $s$ 到 $v$ 的最短距离。

支点一：d[] 沿队列非递减。队列是 FIFO，入队时赋的值总是"队头的 $d$ 值 $+1$"；队头的 $d$ 值随出队单调不减，所以整个队列里的 $d$ 值构成一个非递减序列，且首尾相差至多 1。这意味着 BFS 严格按层号从小到大处理顶点。

支点二：$d[v]$ 是可达的上界，且不可能更小。d[v] = d[u] + 1 说明确实存在一条长度为 d[v] 的 $s\to v$ 路径（沿 path[] 回溯即得），故 $d[v]\ge$ 真实最短距离。反过来，假设真实最短距离是 $\delta <d[v]$，那么最短路径上 $v$ 的前一个顶点 $u^{\prime }$ 满足 $d[u^{\prime }]=\delta -1<d[v]-1=d[u]$。由支点一，$u^{\prime }$ 会先于 $u$ 出队；$u^{\prime }$ 出队时检查到邻居 $v$，若 $v$ 那时还没被访问就会立刻被赋值 $\delta$，若已被访问则说明它更早被赋了一个不超过 $\delta$ 的值。两种情况都与"$v$ 最终的值是 $d[v]>\delta$"矛盾。∎

这个证明用到的唯一图性质是"每条边长度都是 1"——这正是"边权不全相等就不能用"的根源。

变体：统计最短路径的条数

只加一个计数数组：

int cnt[MAX_V];      // cnt[v] = 从源点到 v 的最短路径条数

void BFS_CountPaths(int s, int n) {
    for (int i = 0; i < n; i++) { d[i] = -1; cnt[i] = 0; }
    Queue Q; InitQueue(&Q);
    d[s] = 0; cnt[s] = 1;                  // 源点到自己算 1 条（空路径）
    EnQueue(&Q, s);
    while (!IsEmpty(&Q)) {
        int u; DeQueue(&Q, &u);
        for (int v = FirstNeighbor(u); v >= 0; v = NextNeighbor(u, v)) {
            if (d[v] == -1) {              // 情形 A：第一次到达 v
                d[v] = d[u] + 1;
                cnt[v] = cnt[u];           // 条数继承 u 的
                EnQueue(&Q, v);
            } else if (d[v] == d[u] + 1)   // 情形 B：又发现一条同样短的路
                cnt[v] += cnt[u];          // 累加，不能覆盖
            // d[v] < d[u] + 1：这条路更长，忽略
        }
    }
}

• 情形 B 不能漏，只写 A 会漏掉"从另一个同层前驱走过来"的路径。
• d[v] == d[u] + 1 必须写死，不能只判"已访问"——已访问的顶点也可能是 $u$ 的同层邻居（$d[v]=d[u]$），那条边不构成最短路径的一步。

用走查那张图跑：$cnt[0]=1$；$cnt[1]=cnt[2]=1$；$cnt[3]=1$；$cnt[4]$ 先由 $u=1$ 置为 1，之后 $u=2$ 出队时发现 $d[4]=2=d[2]+1$，于是 $cnt[4]+=cnt[2]=1$，得 $cnt[4]=2$（对应 $0\to 1\to 4$ 与 $0\to 2\to 4$ 两条）；最后 $cnt[5]=cnt[4]=2$。这正好印证了"最短距离唯一、最短路径不唯一"。

考点速记

三条结论：

1. 层号即距离：顶点首次被发现时的层号就是最短距离，这一改造是零额外量级开销的。
2. d[] 与 path[] 必须在入队的同一时刻赋值，否则会重复入队并写坏距离。
3. 只适用于边权全相等的图；边权不等时"边最少"不等于"权和最小"。

这一节在真题里被考过的形式（下方「真题练习」与《BFS》共用同一批题）：

• 等权图上谁能求最短路：给"各边权均为 1 的无向连通图"，在 Prim / Kruskal / BFS 三者里选。答案只有 BFS，而这道题真正要你分清的是最小生成树不是最短路径树——两者优化的目标不同。
• 带权图上 BFS 行不行：作为错误命题出现在四选一里，"可用 BFS 求带权图中每一对顶点的最短路径"是错的。它错了两处：带权不适用，且 BFS 是单源不是全源。

易错：最小生成树 ≠ 最短路径树。 MST 最小化全树权和，最短路径树最小化源点到各顶点的距离。等权环去掉一条边就是最小反例。

易错：边权全相等时 BFS 是可用的，别一看到"带权"就排除它。 判据是"每步代价是否相同"，不是"图上有没有标数字"。

易错：d[v] 与 path[v] 要在入队时赋值。 挪到出队会重复入队，并把已经算对的距离覆盖掉。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p170，§6.6.2 引言： 以交通网为例说明"一位旅客要从 A 城到 B 城，他希望选择一条中转次数最少的路线…… 这个问题反映到图上就是要找一条从顶点 A 到 B 所含边的数目最少的路径。 只需从顶点 A 出发对图做广度优先搜索，一旦遇到顶点 B 就终止。 由此所得的广度优先生成树上，从根顶点 A 到顶点 B 的路径就是中转次数最少的路径"； 同页随即指出，当边被赋权后"路径长度的度量就不再是路径上边的数目，而是路径上边的权值之和"—— 这正是本篇"不能用的情形"的教材依据。
• 同书印刷 p164：BFS 用邻接矩阵存储时 $O(n^2)$、邻接表存储时 $O(n+e)$， "每个顶点至多进一次队列"。

相关知识

BFS 遍历（本篇的算法骨架）｜ Dijkstra 算法（带权推广，普通队列换优先队列）｜ Floyd 算法（全源，可处理负权边）｜ 队列（FIFO 正是"按层处理"的根据）｜ 图的基本概念（距离、路径长度、带权路径长度）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（4题）

2025Q62分2023Q62分2013Q82分2012Q52分