用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径,在算法执行的某时刻,S={0,2,3,4},下一步选取的目标顶点可能是______。
A. 顶点2
B. 顶点3
C. 顶点4
D. 顶点7
没有意义的题
Dijkstra算法的基本思想是每次从距离源点最近的未访问过的顶点开始,更新该顶点的邻居顶点的距离值。
首先,给出带权有向图G的一种可能的形式(权值仅供参考):
根据给定的S={0,2,3,4},表示顶点0、2、3、4已经被访问过。
下一步,我们需要从未访问的顶点中选择一个距离源点(顶点0)最近的顶点。这里可能的选择有:
这里并没有提到顶点1和顶点6的权值,所以无法判断它们是否比顶点5或顶点7更近。但根据给定的选项,我们可以判断:
A. 顶点2:已经被访问过,所以不可能是下一步的目标顶点。 B. 顶点3:同样已经被访问过。 C. 顶点4:同样已经被访问过。 D. 顶点7:是一个可能的目标顶点,因为它还没有被访问,并且可能是距离源点最近的未访问顶点。
所以,正确答案是:D. 顶点7。
友友们这道题是为什么呢
快乐小土狗 回复 哔哔哔: 见楼上回复
哔哔哔 回复 哔哔哔: 辛苦
D
用户登录可进行刷题及查看答案
登录后提交答案