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

学习人数: 4.1k

正确率: ??%

题目描述

未通过

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

A. 顶点2

B. 顶点3

C. 顶点4

D. 顶点7

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

已有12条笔记

2 条评论 (点击展开评论)

2023年10月24日 14:51

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。

2023年10月24日 14:21

友友们这道题是为什么呢

2023年10月24日 14:52

2023年10月25日 17:57