首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
admin
2013-07-12
53
问题
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
法家中重势一派以()为代表。
《关于建国以来党的若干历史问题的决议》对毛泽东和毛泽东思想历史地位的科学评价。
新经济政策的实施表明苏俄()①放弃了由战时共产主义政策过渡到社会主义的设想②发展了马克思主义理论③适时调整生产关系以适应生产力发展④利用市场和商品货币关系发展经济
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
1947年签订的()标志着国际贸易体系的建立,实际上形成了以美国为中心的国际贸易体系。
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
通常通信信道的带宽越大,在数据传输中失真将会()。
设某计算机有四个中断源,优先顺序按1→2→3→4降序排列,若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111,试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求,画出CPU执行程序的轨迹。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
假设Internel的两个自治系统构成的网络如题47图所示,自治系统AS1由路由器R1连接两个子网构成;自治系统As2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、Rl与R3的部分接口IP地址如题47图所示。请回答下列问题。假
随机试题
第二次世界大战以后,国际社会建立国际经济新秩序的一次重大飞跃和明显转折是通过了()
A.甘油B.明胶C.液状石蜡D.聚山梨酯80E.CaCO3可作膜剂成膜材料的是
肩关节脱位慢性骨髓炎
硝酸甘油服用的正确方法为
产品方案主要是指建设项目生产的主导产品的()以及同类产品不同规格、性能、生产能力的优化组合方案。
依据《道路交通安全法》的规定,拖拉机、轮式专用机械车、铰接式客车、全挂拖斗车不得进入高速公路,其他机动车进入高速公路的设计最高时速不低于()公里。
A公司用投资性房地产换入B公司的一项专利权。该项投资性房地产的账面原值为5000万元,已计提折旧1000万元,已计提减值准备500万元。A公司另向B公司支付补价100万元。假设该项资产交换不具有商业实质,A公司换入专利权的入账价值为()万元。
根据我国《票据法》的规定,下列付款方式中,适用于支票的付款方式是()。
左边给定的是纸盒的外表面,下面哪一项能由它折叠而成?
除了何东辉,4班所有的奖学金获得者都是来自西部地区。上述结论可从以下哪项中推出?()
最新回复
(
0
)