用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径,在算法执行的某时刻,S={0,2,3,4},则以后可能修改最短路径是______。
A. 从顶点0到顶点2的最短路径
B. 从顶点0到顶点3的最短路径
C. 从顶点0到顶点4的最短路径
D. 从顶点0到顶点1的最短路径
在Dijkstra算法中,集合S包含了已经确定了最短路径的顶点。对于已经加入集合S的顶点,它们的最短路径不会再被修改。
因此,选项A、B和C中的路径(从顶点0到顶点2、3、4)都已经确定,不会再被修改。
选项D中的路径(从顶点0到顶点1)是可能被修改的,因为顶点1还没有加入集合S,意味着它的最短路径还没有最终确定。在Dijkstra算法的后续步骤中,可能会发现一条从顶点0到顶点1的更短路径,从而修改当前的最短路径估计。
故而正确答案是D. 从顶点0到顶点1的最短路径。
S里面代表0到1~4的距离,迪杰斯特拉算法优先选最短的路径,而S里面最短路径距离就是0,对应的就是0-1这条路径
LukeSu 回复 LukeSu: 还有一种说法是:S={0,2,3,4}表示2、3、4这些顶点已经被访问过,因为它们到起始点的最短路径已经被确定。而顶点1还是0,这意味着顶点1还没有被访问过,它到起始点的最短路径还没有被确定。因此,顶点1的最短路径可能会在以后的步骤中被修改
D
用户登录可进行刷题及查看答案
登录后提交答案