网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。

admin2012-06-26 49

问题网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。

计算机408

学硕统考专业

下列选项不在“万历三大征”之列的是()

抗战以来文艺战线上思想斗争中最重要的问题是()。

希拉克略王朝的军区制改革的内容和意义。

()一书对日月食的记录非常翔实，最早的一次是鲁隐公三年二月(公元前720年2月20日)的日全食，比西方的记录早了130多年。

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

克里特文明的文字类型是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

第二次世界大战结束后，在外国垄断资本对华扩张中取得优势地位的国家是()。

比较工业革命和第二次工业革命，分析英、法、德、美工业革命的过程和特点。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

某蛋鸡场饲喂蛋白质含量为35％的自配饲料，出现产蛋下降和停产等问题，经检查血液中尿酸水平为30mg／dL。该鸡群最可能发生的疾病是

A．知情同意B．支持医学发展C．患者利益至上D．医德境界E．内心信念医德评价方式是

吕某因绑架罪被判处有期徒刑12年。入狱后，吕某认真遵守监规，接受教育改造，确有悔改表现。根据刑法规定，下列对吕某处理错误的是()。

关于项目人力资源管理的说法，正确的有()。

我同《担保法》规定的经济合同的担保形式有(　　)。

某公司在初创时拟筹资200万元，现有甲、乙、丙三个方案可供选择，有关资料如下表所示：根据上述资料，回答下列问题：本案例中该公司筹资决策的依据是()。

一般保证的保证人在主合同纠纷未经审判或者仲裁，并就债务人财产依法强制执行仍不能履行债务前，对债权人可以拒绝承担保证责任。下列情形巾，一般保证的保证人不得行使上述权利的有()。

“应付利息”科目核算的内容是()。

下列各项权利质权，其质权自办理出质登记时设立的有()。

ThephysicalfitnessmovementinAmericafollowedtheimmigrationofalargenumberofGermanmigrantsintoAmericawhofledthe

网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。

计算机408

学硕统考专业

下列选项不在“万历三大征”之列的是()

抗战以来文艺战线上思想斗争中最重要的问题是()。

希拉克略王朝的军区制改革的内容和意义。

()一书对日月食的记录非常翔实，最早的一次是鲁隐公三年二月(公元前720年2月20日)的日全食，比西方的记录早了130多年。

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

克里特文明的文字类型是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

第二次世界大战结束后，在外国垄断资本对华扩张中取得优势地位的国家是()。

比较工业革命和第二次工业革命，分析英、法、德、美工业革命的过程和特点。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

某蛋鸡场饲喂蛋白质含量为35％的自配饲料，出现产蛋下降和停产等问题，经检查血液中尿酸水平为30mg／dL。该鸡群最可能发生的疾病是

A．知情同意B．支持医学发展C．患者利益至上D．医德境界E．内心信念医德评价方式是

吕某因绑架罪被判处有期徒刑12年。入狱后，吕某认真遵守监规，接受教育改造，确有悔改表现。根据刑法规定，下列对吕某处理错误的是()。

关于项目人力资源管理的说法，正确的有()。

我同《担保法》规定的经济合同的担保形式有( )。

某公司在初创时拟筹资200万元，现有甲、乙、丙三个方案可供选择，有关资料如下表所示：根据上述资料，回答下列问题：本案例中该公司筹资决策的依据是()。

一般保证的保证人在主合同纠纷未经审判或者仲裁，并就债务人财产依法强制执行仍不能履行债务前，对债权人可以拒绝承担保证责任。下列情形巾，一般保证的保证人不得行使上述权利的有()。

“应付利息”科目核算的内容是()。

下列各项权利质权，其质权自办理出质登记时设立的有()。

ThephysicalfitnessmovementinAmericafollowedtheimmigrationofalargenumberofGermanmigrantsintoAmericawhofledthe

我同《担保法》规定的经济合同的担保形式有(　　)。