首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
admin
2012-06-26
52
问题
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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
学硕统考专业
相关试题推荐
1543年发表解剖学专著《人体结构论》的是()。
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
明清时期,我国农作物产量有所提高,养活了更多的人口,这种现象并不是由于()。
1918年揭开协约围武装干涉苏维埃俄围序幕的事件是()。
中共八届九中全会提出的恢复和调整国民经济的八字方针,和1979年4月中共中央工作会议中提出的“新八字方针”分别是()。
下列对春秋时期各国称霸的顺序描述错误的选项是()
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
在一个双链表中,在*p结点之前插入*q结点的操作是()。
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
随机试题
简述中国古代原始宗教的种类。
A.引物酶B.连接酶C.解螺旋酶D.单链DNA结合蛋白原核生物复制过程中能解开DNA双链的是
中医治疗,方剂可选用()咳血量甚多,纯血鲜红者,为火热内迫血分,治疗当选方()
关于犯罪嫌疑人、被告人有权获得辩护原则,下列哪些说法是正确的?
甲股份有限公司(以下简称“甲公司”)为一家上市公司,其有关生产线建造及相关租赁业务具体资料如下:(1)为建造一生产线该公司于2011年12月1日从银行借入专门借款1000万元,借款期限为2年,年利率为5%,利息每年支付,假定利息资本化金额按年计算,每年按
网络语言是伴随着网络的发展而新兴的一种有别于传统平面媒介的语言形式。它以简洁生动的形式,一诞生就得到了广大网友的偏爱,发展神速。以下哪一组词不是BBS中跟帖常用的词汇?()。
在数据库中,数据模型包括数据结构、数据操作和
UnderstandingTypesofPoemsⅠ.EpicpoemsA.Definition:—anarrativeconcentratingon【T1】________andeventsthata
A、Areaswithmoresunlight.B、Areaswithrelentlesswaves.C、Areaswithlesslivingseaanimals.D、Areaswithlesshumanactivit
A、It’samobileapplaunchedbyVogue.B、Itletsusersreadnewsonsmartphones.C、ItprovidescontentsfromFacebook.D、Itis
最新回复
(
0
)