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

admin2012-06-26 36

问题网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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://jikaoti.com/ti/phajFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

()属于克利斯提尼改革的内容。

明清时期，我国农作物产量有所提高，养活了更多的人口，这种现象并不是由于()。

有人说：“我们应当以资本供给全世界，而谁以资本供给全世界，谁就应当管理全世界。”讲这话的应该是()。

下列选项中，不属于汉高祖时期的抑商政策的是()

结合史实，分析华北事变前后国民党对日本政策的变化及其主要原因。(华东师范大学2004年中国通史真题)

晚清时期下列武装力量出现的先后顺序是

16世纪奥斯曼土耳其帝国达到顶峰，出现可与当时的中国明朝和哈布斯堡王朝相抗衡的局面，此时在位的苏丹是被称为立法者的()

简述苏联和南斯拉夫之间的冲突。

“二战”爆发的原因是多种因素综合作用的结果，其中最根本的因素是()。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

关于氨基糖苷类抗生素的体内过程正确的是

《(北京大学月刊)发刊词》一文的作者是()

我国成人白血病最常见的是

革兰染色阳性、呈矛头状成双排列、坦面相对的细菌最可能为

人体内O2、CO2进出细胞膜是通过()。

(2010年考试真题)有限合伙人可以按照合伙协议的约定向合伙人以外的人转让其在有限合伙企业中的财产份额，但应当提前30日通知其他合伙人。()

中国第一部交响舞剧是()。

若在产品型式变化少、产品寿命周期长、保管时不易发生损耗、破损时，则需考虑先进先出的管理费用和采用先进先出所带来的效益，两者比较后，再来决定是否要采用先进先出原则。()

教育工作的出发点和归宿是()。