题29

题29

题目

【2012 统考真题】对下图所示的有向带权图,若采用 Dijkstra 算法求从源点 到其他各项点的最短路径,则得到的第一条最短路径的目标顶点是 ,第二条最短路径的目标顶点是 ,后续得到的其余各最短路径的目标顶点依次是 ( ).

A.
B.
C.
D.

分析

没读懂这个题目，什么叫做第一条最短路径，第二条最短路径，这是什么东西？是dijkstra求最短路1-aw里面的哪一个中间步骤的结果
懂了，就是每一次选择的目标点，这里C连通一条边到f，我没看到

解

C
从 到各顶点的最短路径的求解过程下:
后续目标顶点依次为 。
本题也可用排除法: 对于 ,若下一个顶点为 ,路径 的长度为 5,而 的长度仅为 4,显然错误。同理可排除选项 B。将 加入集合 后,采用上述方法也可排除选项 D。

顶点	第 1 轮	第 2 轮	第 3 轮	第 4 轮	第 5 轮
	5
	oo		7	7
	oo
集合S