首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
admin
2012-06-26
55
问题
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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
学硕统考专业
相关试题推荐
春秋后期的()用望、闻、问、切的方法诊断病人。
标志着清政府被迫放弃闭关政策,开始面向世界,基本上完成了从传统的理藩向近代外交转化的事件是1861年()。
下列选项中,()不是共产党抗日民族统一战线的土地政策的三条基本原则之一。
陈垣先生著《元也里可温考》一书中讲述了元代某种西方宗教传人内地的情形,“也里可温”指的是()。
新中国成立以后至今经历的历史发展阶段有()。
简述中华人民共和国成立初期在政权巩固方面所采取的主要措施及其意义。(华东师范大学2004年中国通史真题)
下列选项中,控制了西域政权的是()
下列选项不属于封臣对封君义务的是()。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
某激光打印机每分钟打印20页,每页4000字符,相应的设备驱动程序一次输出一个字符,采用中断方式,CPU处理每次中断需50微秒,则CPU用于打印的开销是()。
随机试题
回心血量增加使心肌收缩加强属于
海浮石的功效有
临床诊断乳牙根尖周病不依赖于
某市政府部门决定采用招标方式而不采用拍卖方式出让国有土地使用权用于开发建设商住楼,这是因为招标方式有利于()。[2011年真题]
某企业有4个独立的投资方案A、B、C、D,可以构成()个互斥方案。
( )是建设项目内部控制的基本目标。
下列有关工程计量的说法中,符合规定的是()。
根据票据法律制度的规定,下列各项中,取得票据的人不得享有票据权利的有()。
西服套装
TodayI’dliketotalkaboutwhathelpspeoplesuccessfullyintegrateintoanewculture.Whereasthereasonsformigrationare
最新回复
(
0
)