给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，给定V中的一个顶点A，称为源，求从源顶点A出发到其他各顶点的最短路径长度称为单源最短路径长度问题。关于单源最短路径问题的Dijkstra 算法， 下面哪些描述是正确的？
A: 设定一个顶点集合S，初始时，S={A}，每次从V-S中选择顶点加入S， 直到全部加入，算法结束。
B: 每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点，也就是V-S集合中最短特殊路径长度最小的顶点，通常算法中用dist[] 数组记录各顶点的最短特殊路径长度。
C: 每次从V-S集合选择加入S集合的顶点是V-S集合中的顶点同S集合的顶点连接边最短的，通常算法中用dist[] 数组记录S集合中各顶点与V-S集合中各顶点的最短连接边。
D: 每次选择一个顶点加入S集合后， 都要检查是否需要更新dist[]数组元素的值
A: 设定一个顶点集合S，初始时，S={A}，每次从V-S中选择顶点加入S， 直到全部加入，算法结束。
B: 每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点，也就是V-S集合中最短特殊路径长度最小的顶点，通常算法中用dist[] 数组记录各顶点的最短特殊路径长度。
C: 每次从V-S集合选择加入S集合的顶点是V-S集合中的顶点同S集合的顶点连接边最短的，通常算法中用dist[] 数组记录S集合中各顶点与V-S集合中各顶点的最短连接边。
D: 每次选择一个顶点加入S集合后， 都要检查是否需要更新dist[]数组元素的值
举一反三
- Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
- 用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻：S={0，2，3，4}，选取的目标顶点是顶点1则可能修改最短路径是（ ）。 A: 从顶点0到顶点2的最短路径 B: 从顶点2到顶点4的最短路径 C: 从顶点0到顶点1的最短路径 D: 从顶点0到顶点3的最短路径
- 【单选题】给定一个无向连通带权图G=(V,E),下述关于prim算法说法不正确的是( )。 A: prim算法先选出一个顶点加入到集合S,把图的顶点分成两个集合,一个S,一个V-S B: prim算法总是选择连接S和V-S的边中权最小的加入到最小生成树中。 C: prim算法停止的条件是S=V D: prim算法的时间复杂度O(n3),n为图的顶点个数。
- 用 Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的 某时刻，S={0,2,3,4}，选取的目标顶点是顶点1，则可能修改的最短路径是( )
- 用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径,在算法执行的某时刻:S={0,2,3,4}下一步选取的目标顶点可能是()。 A: 顶点7 B: 顶点3 C: 顶点4 D: 顶点2