不是VIP会员，不能显示答案

题目解答

题目：
对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程中还会出现的值有（ ）。
  • A.3
  • B.7
  • C.6
  • D.5
考点： 0
分析：
解答： 解析：此题考查图论当中求单源最短路径的算法Dijkstra算法的掌握程序。
Dijkstra的思想是建个一维数组记录起点到其他各点的距离（没路为无限大），然后找一个这个距起点最近的点作为中间结点，更新起点到各个点的距离，然后把中心结点加个用过的标记，继续找下一个距离起点最近的点为中心结点，直到所有的点都当过中心结点就结束。这题中，第一个找到的中间结点是A，这时把SB更新为7，然后找到的中心结点为D，这时把SB更新为6，把SC更新为4；下一个找到的中心结点为C，这时把SB更新为5。所以选BCD。
初开始：SA=2，SB=8，SC=∞，SD=3
第一次取最小边SA则更新为：SA=2，SB=7，SC=∞，SD=3
第二次取最小边SD则更新为：SA=2，SB=6，SC=4，SD=3
第一次取最小边SC则更新为：SA=2，SB=5，SC=4，SD=3
评论：
老师： 0