题35
题目
【2016 统考真题】使用 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
分析
根据 Dijkstra 算法, 从顶点 1 到其余各顶点的最短路径如下表所示。
注意这是要回退的，如果当前的点没有出度了，就要回退到上一个点，所以最终的路径是 1→5→2→3→6→4
3过后的6以及4就是退出来，重新进入到5扫描的这两个出度
解
B
快速解法：
依次观察从顶点 1 到其他顶点的最短路径长度: 顶点 1 到顶点 2 的最短路径长度为 5 ;
顶点 1 到顶点 3 的最短路径长度为
顶点 1 到顶点 4 的最短路径长度为 11 ;
顶点 1 到顶点 5 的最短路径长度为 4 ;
顶点 1 到顶点 6 的最短路径长度为
最终 dist[] = {0,5,7,11,4,9} ,根据 dist 数组值从小到大选择顶点顺序为 1,5,2,3,6,4