网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。

admin2013-07-12 49

问题网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。

选项

答案本题利用Dijkstra算法求出最短路径树，从而得到结点A路由表。计算过程如下： [*]

解析 Dijkstra算法是一种求单源最短路径树的算法，是()SPF、路由协议的核心算法，该算法基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。
在以下算法中，s为源，w[u，v]为点u和v之间的边的长度，结果保存在dist[]
(1)初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
(2)循环n－1次：
在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
对于每个与u相邻的点v，执行Relax(u，v)，也就是说，如果dist＋w[u，v]＋w[，u，v]。此时到点v的最短路径上，前一个节点即为u。
(3)结束。此时对于任意的u，dist就是s到u的距离。

转载请注明原文地址:https://kaotiyun.com/show/0uxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。

计算机408

学硕统考专业

以下古代文件起到了限制王权作用的是()。

简述蒙古西征的具体过程及其对中亚等地区的影响。(东北师范大学1999年世界中古史真题；南京大学2001年综合卷真题；东北师范大学2002年世界中古史真题)

波兰三次被瓜分的时间是()

在努力纠正“文化大革命”错误的过程中，遇到的严重障碍是()

永元四年(公元92年)，汉和帝用宦官()掌握的一部分禁军，消灭了窦氏势力。郑众从此参与预政事，并受封为侯，这是宦官用权和封侯的开始。

在西北地区，西北野战军采取了蘑菇战术与敌人周旋，这实际上是()。

适宜用于外形复杂或异形截面的混凝土构件及冬期施工的混凝土工程的常见模板是()。

适合涉及多个专业领域，并需要周密控制的项目是()

Donotdisturbme.I_____lettersallmorningandhavewrittentensofar.

A．胃体B．小网膜囊C．肝左叶D．横结肠及其系膜E．肠系膜上动脉胰腺体部前方紧邻

下述哪一项不是儿童糖尿病的临床特点

如下哪项是诊断类风湿性关节炎较有价值的检查

(2014)有压管流模型试验，如果用比例为10的水平放置模型水管，测得单位长度的压力损失为14．6Pa／m，则水温不变，原型单位长度的水管压力损失为()。

_______为学生的学习活动提供了基本线索，是实现课程目标、实施教学的重要资源。

我国古代的四大发明不包括()

4，10，30，105，420，()。