用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻，S={0，2，_

学习人数: 3.9k

正确率: ??%

题目描述

未通过

用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻，S={0，2，3，4}，则以后可能修改最短路径是______。

A. 从顶点0到顶点2的最短路径

B. 从顶点0到顶点3的最短路径

C. 从顶点0到顶点4的最短路径

D. 从顶点0到顶点1的最短路径

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

已有13条笔记

1 个回答 (点击展开回答)

2023年12月10日 01:12

S里面代表0到1～4的距离，迪杰斯特拉算法优先选最短的路径，而S里面最短路径距离就是0，对应的就是0-1这条路径

LukeSu 回复 LukeSu：还有一种说法是：S={0，2，3，4}表示2、3、4这些顶点已经被访问过，因为它们到起始点的最短路径已经被确定。而顶点1还是0，这意味着顶点1还没有被访问过，它到起始点的最短路径还没有被确定。因此，顶点1的最短路径可能会在以后的步骤中被修改

2023年12月10日 01:22