首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
admin
2012-06-26
83
问题
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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://kaotiyun.com/show/Yfxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()属于克利斯提尼改革的内容。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
保加利亚共产党于1990年4月改名为保社会党,它在政府中沦为少数派的时间是()。
论述彼得一世改革的背景、措施及影响
提出行星绕太阳运行为椭圆形轨道的天文学家是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:写出图G的邻接矩阵A。
随机试题
关于模板工程设计主要原则的说法,正确的是()。
互联网媒体的优点和缺点分别是()
每当我学习中遇到困难,他总是来帮助我。
器质性头痛病人的护理措施正确的是
为实现某种特定目的,投入资金和资源,在规定的期限内建造或购置固定资产的一整套活动,称为()。
某工程工作内容为修建一条公路和跨越公路的人行天桥,合同总价4000万元,合同工期20个月。施工中发生了以下情况:(1)由于图纸错误,监理工程师通知一部分工程暂停,拖延工期1.5个月。(2)由于高压线需要电力部门同意迁移后才能施工,造成工程延
基坑支护破坏的主要形式有()引起的破坏。
人是具有自我意识,发展到一定阶段的人,具有规划自己的未来和为未来的发展创造条件的能力。由此表明,人的身心发展具有()
信息系统的软件需求说明书是需求分析阶段最后的成果之一,()不是软件需求说明书应包含的内容。
Evenasaleaderathome,itwon’tbeeasyforthecompanytoestablishthatsamekindof_______inotherareas.
最新回复
(
0
)