第 7 题
对如下有向图带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余最短路径的目标顶点依次是（ ）。
A. d, e, f
B. e, d, f
C. f, d, e
D. f, e, d
[tag_link]
正确答案：C
从 a 到各顶点的最短路径的求解过程：
| 顶点 | 第 1 趟 | 第 2 趟 | 第 3 趟 | 第 4 趟 | 第 5 趟 |
|---|---|---|---|---|---|
| b | (a,b)2 | ||||
| c | (a,c)5 | (a,b,c)3 | |||
| d | ∞ | (a,b,d)5 | (a,b,d)5 | (a,b,d)5 | |
| e | ∞ | ∞ | (a,b,c,e)7 | (a,b,c,e)7 | (a,b,d,e)6 |
| f | ∞ | ∞ | (a,b,c,f)4 | ||
| 集合 S | {a,b} | {a,b,c} | {a,b,c,f} | {a,b,c,f,d} | {a,b,c,f,d,e} |
后续目标顶点依次为 f,d,e。第三轮已有 dist(f)=4<dist(d)=5<dist(e)=7，先固定 f；随后固定 d，并把 e 更新为路径 a→b→d→e、长度 6；最后固定 e。因此选 C。