首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
admin
2012-06-26
34
问题
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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年()。
英、法这两个昔日战场上并肩作战的盟友却在巴黎和会上怒目相对,甚至以退出和会相要挟,两国的矛盾焦点是()。
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
下列政权中,控制西域的政权是()。
叙述并评价二战后西欧主要国家的“福利国家”政策。
晚清时期下列武装力量出现的先后顺序是
评述从五四运动到中国共产党成立,马克思主义在中国传播的情况及其原因。
洋务派创办军事工业的方式是()。
《道威斯计划》的实施所产生的直接结果是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
影响链斗挖泥船运转小时生产率的主要参数有()。
下列关于林分质量调整系数K说法正确的有()。
《___》问世之后成为“希腊的圣经”。
肾上腺皮质功能亢进时不出现
一医生在为其患者进行眼科手术的前一夜,发现备用的眼球已经失效,于是到太平间看是否有新鲜的尸体供眼球移植之用,恰巧有一尸体。考虑到征得死者家庭意见很可能会遭到拒绝,而且时间也紧迫,于是便取出了死者的一侧眼球,然后用义眼代替。尸体火化前,死者家庭发现此事,便把
A.对半卡环B.圈形卡环C.三臂卡环D.回力卡环E.联合卡环前后均有缺牙间隙的孤立后牙上的卡环宜采用
医务人员正确的功利观不包括
“名例律”作为中国古代律典的“总则”篇,经历了发展、变化的过程。下列哪一表述是不正确的?
税收的基本特征不包括()。
简述SWOT分析模型及其在企业战略选择中的应用。
最新回复
(
0
)