请在 下方输入 要搜索的题目:

给定带权有向图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[]数组元素的值

发布时间:2024-09-05 17:54:51
推荐参考答案 ( 由 题搜搜 官方老师解答 )
答案:设定一个顶点集合S,初始时,S={A},每次从V-S中选择顶点加入S, 直到全部加入,算法结束。 ■每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点,也就是V-S集合中最短特殊路径长度最小的顶点,通常算法中用dist[] 数组记录各顶点的最短特殊路径长度。 ■每次选择一个顶点加入S集合后, 都要检查是否需要更新dist[]数组元素的值
登录 - 搜搜题库网
立即注册
注册 - 搜搜题库网
立即登录