题目

使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径，将当前找到的从顶点 1 到顶点 2, 3, 4, 5 的最短路径长保存在数组 dist 中，求出第二条最短路径后，dist 中的内容更新为( )。

图的文字版（与上图等价）：顶点为 1, 2, 3, 4, 5，所有边均为有向边并标注权值：

• 1 → 5（权 6）、1 → 2（权 26）、1 → 3（权 3）
• 5 → 2（权 15）、5 → 4（权 8）
• 4 → 3（权 6）、4 → 2（权 1）
• 3 → 2（权 22）

错因

A

漏掉了用新加入的顶点松弛 dist[2]。求出第 1 条最短路径（dist[3]=3）和第 2 条最短路径（dist[5]=6）后，应当用 3 和 5 的出边去更新 dist。选 A 的人保留了 dist[2] = 26 的初始值（直接边 1→2 的权），相当于这两次松弛全没做。

B

只做了第 1 步松弛、漏了第 2 步。第 1 步 dist[3]=3 加入后，通过 3→2 边把 dist[2] 从 26 松弛到 25 是对的；但第 2 步 dist[5]=6 加入后，5→2 边能把 dist[2] 从 25 进一步松弛到 21（=6+15），选 B 的人停在了 25。Dijkstra 每加入一个新顶点就要对其所有出边做松弛，跳一步都不行。

D

直接抄了 5→2 这条边的边权 15，忘记加 1→5 的距离。dist[2] 表示的是"从源点 1 到 2 的累计距离"，等于"到中间点 5 的距离 + 边 5→2 的权"= 6 + 15 = 21，不是 15。这是初学者套 Dijkstra 时最容易栽的坑：把"边权"当成"路径长度"。

总解析

思路：Dijkstra 维护两个集合——已确定最短路径的 S 和未确定的 V−S。每轮从 V−S 中选 dist 最小的顶点 u 加入 S，然后用 u 的所有出边松弛（relax）邻居：if dist[u] + w(u,v) < dist[v]: dist[v] = dist[u] + w(u,v)。"求出第 k 条最短路径"= 第 k 次把顶点加入 S。

初始化（从源点 1 出发，S = {1}，dist[1]=0）：

顶点	dist 初值	来源
2	26	直接边 1→2
3	3	直接边 1→3
4	∞	1 不直接到 4
5	6	直接边 1→5

第 1 步：找出第 1 条最短路径。

V−S = {2, 3, 4, 5}，dist 最小者是 3（dist[3]=3）。把 3 加入 S。 用 3 的出边 3→2（权 22）松弛：dist[2] = min(26, 3+22) = 25。

顶点	2	3	4	5
dist	25	3	∞	6

1→3 路径长度 = 3，是从源点出发的第 1 条最短路径。

第 2 步：找出第 2 条最短路径。

V−S = {2, 4, 5}，dist 最小者是 5（dist[5]=6）。把 5 加入 S。 用 5 的出边松弛：

• 5→2（权 15）：dist[2] = min(25, 6+15) = 21
• 5→4（权 8）：dist[4] = min(∞, 6+8) = 14

顶点	2	3	4	5
dist	21	3	14	6

1→5 路径长度 = 6，是从源点出发的第 2 条最短路径。

第 3 步及之后（题不要求，但可验证收敛）：下一步选 dist[4]=14 加入 S，用 4 的出边继续松弛 dist[2] 和 dist[3]（注意 4→2 的边权很小可能进一步把 dist[2] 压低）；最后选 dist[2] 加入。本题只问到第 2 步结束的状态。

最终答案：求出第 2 条最短路径后，

最终答案是 C（21, 3, 14, 6）。

核心要点：每次"加入新顶点"后都要立刻对其所有出边松弛，dist 数组才能反映"从源点经已知最短路径到达该顶点的最优距离"。漏一次松弛，整张表就会偏。