题目

使用迪杰斯特拉(Dijkstra)算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是( )。

错因

A

前三步（5, 2, 3）算对了，但漏掉了 3 → 6 这条出边。在第四轮选取最近顶点时，正确做法是先用 3 的出边更新 ，再比较 和 选 6。如果忘了更新 ， 仍为 ，那剩下未选顶点中只有 是有限值，自然误选 4。错的不在 Dijkstra 流程，而在"加入新顶点后必须用它的所有出边松弛"这一步。

C

第二步（选完 2）之后漏掉了 2 → 3 的松弛。本应通过 2 把 从 更新为 ，但选 C 的人没做这步，结果 仍是 ，比较时只看 是唯一有限值，误把 4 当成第三近。本质和 A 是同一类错误的不同位置：每加一个新顶点都必须用它的出边更新所有可达邻居。

D

第二步算 2 是对的，但第三步直接跳到 6，跳过了 3。可能的思路是混淆了"路径"和"目标"——把""或""看成最短路径，但事实上图里没有 、 这种直达边，到 6 必须经 3。也可能把 错算成 等错的中间值。Dijkstra 第三步的关键是按 值大小选最小的未访问顶点，不能跳号选。

总解析

Dijkstra 算法：从源点开始，每轮"贪心"选取当前 值最小的未访问顶点 加入已确定集 ，然后用 的所有出边松弛 的邻居。重复直到所有顶点入 。

初始化：，其它顶点 ，。

逐轮模拟：

第 1 轮：未访问中 最小的是 1（）。加入 1 到 。

用 1 的出边 、 更新：

顶点	1	2	3	4	5	6
	0 ✓	5	∞	∞	4	∞

第 2 轮：剩余中 最小是 5（）。第 1 个被选定的目标：5 ✓

用 5 的出边 、 更新：

顶点	1	2	3	4	5	6
	0 ✓	5	∞	11	4 ✓	∞

第 3 轮：剩余中 最小是 2（）。第 2 个：2 ✓

用 2 的出边 、 更新：

顶点	1	2	3	4	5	6
	0 ✓	5 ✓	7	11	4 ✓	∞

第 4 轮：剩余中 最小是 3（）。第 3 个：3 ✓

用 3 的出边 、 更新：

顶点	1	2	3	4	5	6
	0 ✓	5 ✓	7 ✓	11	4 ✓	9

第 5 轮：剩余 4（）和 6（）。第 4 个：6（）✓

用 6 的出边 更新：无变化。

第 6 轮：只剩 4（）。第 5 个：4 ✓

最终选取顺序：。

关键易错点：第 4 轮选最小时，必须先用 3 的出边松弛 （从 降到 9），再和 比较。如果跳过这一步，就会得到选项 A 的错误顺序。

最终答案是 B（5, 2, 3, 6, 4）。