首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
admin
2012-06-26
60
问题
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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
学硕统考专业
相关试题推荐
希拉克略王朝的军区制改革的内容和意义。
评述欧洲一体化的历史进程。(华东师范大学1998年世界当代史真题)
简述布匿战争的过程。
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
在19世纪60年代到90年代,洋务派兴办洋务事业的主要目的是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
某激光打印机每分钟打印20页,每页4000字符,相应的设备驱动程序一次输出一个字符,采用中断方式,CPU处理每次中断需50微秒,则CPU用于打印的开销是()。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
某32位计算机系统采用段页式虚拟存储管理,现有一个进程被分成5段,其段号和段长见下表,段内分页,页表见下,存放在内存中,每页的长度为4096B。进程运行到某一个指令,其地址为(2,3,010),当前CPU的寄存器和地址加法器的状态如图所示,当上述指令执行时
随机试题
甲乙二人结婚后,甲父出资为甲购买了一栋房屋,并且将产权登记在甲的名下,此后,甲乙一直生活在该房屋中。后甲乙感情不和,欲离婚,对房屋所有权的归属产生争议,下列说法正确的是()
新兴公司有一台设备既可生产甲产品也可生产乙产品。若甲、乙两种产品在各年末发生的现金净流量资料如下表所示:该公司的预期投资报酬率为16%。要求:利用净现值法判断生产哪种产品较为合适。
正常前列腺液镜检时可见大量
A.精制谷类、牛奶、鸡蛋、绿叶蔬菜 B.畜、禽类、鱼虾、干豆类 C.肝、肾、脑、肉汤类 D.蜂产品 E.酶制剂痛风病人绝对禁止食用的食物是()。
兽药经营许可证有效期为()年。有效期届满,需要继续经营兽药的,应当在许可证有效期届满前6个月到原发证机关申请换发兽药经营许可证
血虚月经后期的首选方是
甲公司为居民企业。2017年有关收支情况如下:(1)产品销售收入5000万元,营业外收入150万元。(2)发生合理的工资薪金300万元、职工供暖费补贴46万元、防暑降温费40万元。助(3)发生广告费600万元,税收滞纳金12万元、环保部
废除沿用了1300年的科举制的是:
甲:从互联网上人们可以获得任何想要的信息和资料。因此,人们不需要听取专家的意见,只要通过互联网就可以很容易地学到他们需要的知识。乙:过去的经验告诉我们:随着知识的增加,对专家的需求也相应地增加。因此,互联网反而会增加我们咨询专家的机会。
下面关于图(网)的叙述,正确的是()。
最新回复
(
0
)