题目

对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余最短路径的目标顶点依次是( )。

错因

A

按节点编号 d, e, f 顺序"猜"。可能没注意到 c→f 这条短边（权 1），以为 f 离起点最远应该最后被确定。但 Dijkstra 是"按 值贪心选择"，不按图上的物理远近——通过 c 转一下，f 的距离只有 4，比 d (5) 和 e 都近。

B

把 e 排在 d 前面。可能想：从 c 出发 c→e=4 直接松弛到 d[e]=7，看着 e 准备好了。但只有当一个节点的 d 值是当前未确定集合中的最小值才能被选中，d[e]=7 比 d[f]=4 大、比 d[d]=5 也大，e 必须排在最后。

D

把 d 和 e 的先后弄反。e 的 d 值只有等到 d 被确定后通过 d→e:1 松弛才会从 7 缩到 6（也就是 d[e]=5+1=6）。d 必须先于 e 被选中，所以 d 应该在 e 之前。选 D 等于忽略了"d 节点是 e 的关键中转"。

总解析

Dijkstra 算法核心：维护数组 （已知 a 到 v 的最短距离），每轮挑出未确定节点中 值最小者固化进结果集（"被确定"），并用它松弛邻居。

逐轮模拟：

轮次	本轮选中							松弛说明
初始	—	0	∞	∞	∞	∞	∞
1	a (0)	0	2	5	∞	∞	∞	a→b:2, a→c:5
2	b (2)	0	2	3	5	∞	∞	b→c:1（路径 a→b→c=3 比直走 a→c=5 短）；b→d:3
3	c (3)	0	2	3	5	7	4	c→f:1（3+1=4）；c→e:4；c→d:3（5 仍最优不更新）
4	f (4)	0	2	3	5	7	4	f 没有出边可松弛
5	d (5)	0	2	3	5	6	4	d→e:1（5+1=6 比 7 短）
6	e (6)	0	2	3	5	6	4	全部确定

确定顺序：a → b → c → f → d → e

关键反直觉点：f 在图上看着"最远"，但有 c→f:1 这条短边，经 b→c 之后只需再走 1 就到 f，总距离 4，比 d (5) 和 e (6) 都早确定。Dijkstra 按 值贪心而不按物理位置。

题目说前两条已知（b、c），后续依次是 f, d, e。

最终答案是 C。

最短路径树（高亮路径，灰化无关边）：