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

admin2013-07-12 56

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

学硕统考专业

利玛窦与李之藻合译的()一书，介绍了西方数学中的算术知识，尤为可贵的是，其传入了中国所没有的西洋笔算法。

我国古代文献中记载了许多有关部落和部落联盟之问发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

法家中重势一派以()为代表。

马克思指出：“鸦片不曾产生催眠的作用，而倒产生了惊醒作用，历史的发展好像首先要麻醉这个国家的人民，然后才可能把他们从历来的麻木状态唤醒似的。”这里所说的“唤醒”的意思是()。

下列对西汉察举制度的评述，错误的是()

简评斯大林《苏联社会主义经济问题》。

略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)

“瓜步之战”发生在下列哪两个政权之间?()

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

构音异常有多种不同表现，下列不正确的是()

＝________．

“扬州画派”的产生是由于当时扬州的()

A、2～10℃B、10～30℃C、＜20℃D、遮光、＜20℃E、巴曲酶冷处应（）。

过期妊娠指妊娠达到或超过

税收作为一种经济活动，属于经济基础范畴；而税法则是一种法律制度，属于上层建筑范畴。()

根据沟通手段的不同，沟通可以划分为()。

依据我国社会主义初级阶段生产力落后的实际情况，我们必须()。