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

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

admin2013-07-12  104
问题 网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用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://www.kaotiyun.com/show/0uxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)