文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > Dijkstra算法
侵权投诉

Dijkstra算法

Dijkstra算法

5.3.4 附录E 最短路径算法——Dijkstra算法

在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个,即Bellman-Ford算法和Dijkstra算法。这两种算法的思路不同,但得出的结果是相同的。我们在下面只介绍Dijkstra算法,它的已知条件是整个网络拓扑和各链路的长度。 应注意到,若将已知的各链路长度改为链路时延或费用,这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此,求最短路径的算法具有普遍的应用价值。

Dijkstra算法

令v部分:

若结点 v 与结点 1 不直接相连

在用计算机进行求解时,可以用一个比任何路径长度大得多的数值代替∞。对于上述例子,

可以使D(v) = 99。

(2) 寻找一个不在N中的结点w,其D(w)值为最小。把w加入到N中。然后对所有不在N中的结点v,用[D(v), D(w) + l(w, v)]中的较小的值去更新原有的D(v)值,即:

D(v)←Min[D(v), D(w) + l(w, v)] (E-1)

(3) 重复步骤(2),直到所有的网络结点都在N中为止。

表E-1是对图E-1的网络进行求解的详细步骤。可以看出,上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D(w) 值。当第5次执行步骤(2)并得出了结果后,所有网络结点都已包含在N之中,整个算法即告结束。

表E-1 计算图E-1的网络的最短路径

Dijkstra算法

第1页

你可能喜欢

  • Dijkstra算法代码
  • 机器人避障
  • 迪杰斯特拉算法
  • 算法的C语言实现
  • 最短路径算法
  • 数学建模
  • 最小生成树算法

热门文档

相关文档

  • Dijkstra算法

    Dijkstra算法_IT/计算机_专业资料。Dijkstra算法 Dijkstra算法能求一个顶点到另一顶点最短路径。 它是由Dijkstra于1959年提出的。实际它能出始点到 其它所有...

  • Dijkstra算法的流程图及算法代码

    Dijkstra算法的流程图及算法代码_数学_自然科学_专业资料。Dijkstra算法的流程图及算法代码开始 定义全局变量 dist[N], v0,cost[N][N] 初始化变量 final[N]...

  • Dijkstra算法

    Dijkstra算法_小学教育_教育专区。Dijkstra算法 Dijkstra算法一、Dijkstra算法与最短路问题 二、 Dijkstra算法的概念与思想 三、 Dijkstra算法的实现步骤 Dijkstra...

  • Dijkstra算法图解

    Dijkstra算法图解_互联网_IT/计算机_专业资料。5.3.4 附录 E 最短路径算法——Dijkstra 算法 在路由选择算法中都要用到求最短路径算法。最出名的求最短路径...

  • Dijkstra算法的流程图

    Dijkstra算法的流程图_高二语文_语文_高中教育_教育专区。dijkstra算法流程图,经典Dijkstra 算法的流程图 需求和规格说明: 需求和规格说明: Dijkstra 算法是典型最...

  • Dijkstra算法的完整实现版本之算法的源代码

    Dijkstra 算法的完整实现版本之算法的源代码 样例图: 输入格式: 输出格式: 输入时,将 s,t,x,y,z 五个点按照 1,2,3,4,5 起别名,输入格式按照下图例所示...

  • Dijkstra算法

    长度为 。 最短通路为: 最短通路为: (a,b,c), d(a,c)=9 3 d c Dijkstra算法 算法是有限带权图, ? 定义 设G是有限带权图,S?V(G),u0∈S, ...

  • Dijkstra算法图示

    Dijkstra 算法学习笔记 Dijkstra 算法是一种最短路径算法,用于计算一个节点到其它所有节点的最短 路径,动态路由协议 OSPF 中就用到了 Dijkstra 算法来为路由计算最...

  • Dijkstra算法的实现

    Dijkstra算法的实现_IT/计算机_专业资料。题目:Dijkstra 算法的实现 题目 一、 问题分析和任务定义 1.1 题 1.2 要目:对任意图,选择合适的数据结构表示图,...

  • Dijkstra算法的实现-数据结构与算法课程设计报告

    Dijkstra算法的实现-数据结构与算法课程设计报告_计算机软件及应用_IT/计算机_专业资料。数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email