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

admin2012-06-26 84

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

学硕统考专业

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

1918年揭开协约围武装干涉苏维埃俄围序幕的事件是()。

有人说：“我们应当以资本供给全世界，而谁以资本供给全世界，谁就应当管理全世界。”讲这话的应该是()。

尼克松执政期间美国对外战略进行重大调整的根本原因是()。

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

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

拉美独立战争中，委内瑞拉地区一位著名领导人，他曾经领导建立委内瑞拉第二和第三共和国，这位领导人是()。

罗马帝国疆域扩张到顶点是在()统治时期。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

计算机有线网络目前通常采用的传输介质有()。

某有限责任公司的股东甲拟向公司股东以外的人A转让其出资。下列关于甲转让出资的表述中，符合公司法律制度规定的是()。

李某2009年3月以60万元的价格购买了两处房产作为投资，2013年5月以50万元的价格将其中一处房产出售给郑某，签订了产权转移书据。郑某在此次房屋交易中应缴纳的税种有()。

【2015中国银行】()对于“纠纷”相当于“垄断”对于()

学生林某放在课桌里的钱包不见了，于是班主任就对全班同学进行搜身。班主任的做法侵犯了学生的()。

(2006年多选48)下列关于我国法律监督的表述，正确的有()。