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

admin2012-06-26 70

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

选项

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

解析 Dijkstra算法是一种求单源最短路径树的算法，是OSPF路由协议的核心算法，该算法基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。
在以下算法中，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://www.kaotiyun.com/show/Yfxi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

文艺复兴运动兴起的时间是()。

简述布匿战争的过程。

文艺复兴时期，系统提出了国家主权理论的政治思想家是()。

()一书对日月食的记录非常翔实，最早的一次是鲁隐公三年二月(公元前720年2月20日)的日全食，比西方的记录早了130多年。

西汉时期，张骞第一次出使西域的主要目的是()

19世纪末20世纪初，在外国侵华势力中占主要地位的是()。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

晚清时期清帝年号的正确排序是

在网络中计算机接收的信号是()。

下面不属于社会主义核心价值观的是()。

really

Anemployerhasseveralchoiceshecanconsiderwhenhewantstohireanewemployee.First,hemaylookwithinhisowncompany.

改善法洛四联症患儿麻醉后低氧血症最有效的措施是

根据《水利水电工程标准施工招标文件》，招标文件对分包的要求不包括()。

调节国际收支失衡的主要宏观政策措施有()。

下列自然保护区不属于自然风景型的是()。

竞技体操比赛中，自由体操场地的长和宽均为12米。()

算法执行过程中，所需要的基本运算次数称为算法的【】。