第 8 题
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。
A. 5, 2, 3, 4, 6 B. 5, 2, 3, 6, 4 C. 5, 2, 4, 3, 6 D. 5, 2, 6, 3, 4
[tag_link]
正确答案：B
根据 Dijkstra 算法，从顶点 1 到其余各顶点的最短路径如下表所示。
| 顶点 | 第 1 趟 | 第 2 趟 | 第 3 趟 | 第 4 趟 | 第 5 趟 |
|---|---|---|---|---|---|
| 2 | 5v1→v2 | 5v1→v2 | |||
| 3 | ∞ | ∞ | 7v1→v2→v3 | ||
| 4 | ∞ | 11v1→v5→v4 | 11v1→v5→v4 | 11 v1→v5→v4 | 11v1→v5→v4 |
| 5 | 4v1→v5 | ||||
| 6 | ∞ | 9v1→v5→v6 | 9v1→v5→v6 | 9v1→v5→v6 | |
| 集合 S | {1, 5} | {1, 5, 2} | {1, 5, 2, 3} | {1, 5, 2, 3, 6} | {1, 5, 2, 3, 6, 4} |
顶点 1 到其余顶点的最终最短距离分别为 d(5)=4、d(2)=5、d(3)=7、d(6)=9、d(4)=11。Dijkstra 每轮固定当前暂定距离最小的未确定顶点，因此顺序为 5,2,3,6,4，选 B。