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

学习人数: 4.4k

正确率: 69%

题目描述

未通过

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

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

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

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

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

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

已有16条笔记

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

2024年8月29日 10:47

在Dijkstra算法中，集合S包含了已经确定了最短路径的顶点。对于已经加入集合S的顶点，它们的最短路径不会再被修改。

因此，选项A、B和C中的路径（从顶点0到顶点2、3、4）都已经确定，不会再被修改。

选项D中的路径（从顶点0到顶点1）是可能被修改的，因为顶点1还没有加入集合S，意味着它的最短路径还没有最终确定。在Dijkstra算法的后续步骤中，可能会发现一条从顶点0到顶点1的更短路径，从而修改当前的最短路径估计。

故而正确答案是D. 从顶点0到顶点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