最短路问题-迪杰斯特拉算法.ppt

该【最短路问题-迪杰斯特拉算法 】是由【wxq362】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【最短路问题-迪杰斯特拉算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。最 短 路 问 题
问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数最小的通路。（注意：在有向图中，通路——开的初等链中所有的弧应是首尾相连的。）
应用背景——管道铺设、线路安排、厂区布局、设备更新等。
一、问题的提法及应用背景
二、最短路算法
1． D氏标号法（Dijkstra）；边权非负
2. 列表法（福德法）；有负权，无负回路
4
v1
v2
v3
v4
v6
v5
v7
2
2
5
6
1
4
1
3
4
1
2
（2）使用条件——网络中所有的弧权均
非负，即 。
1．D氏标号法（Dijkstra）
（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。
选用符号的意义：
P 标号（Permanent固定/永久性标号）
——从始点到该标号点的最短路权
T 标号（Temporary临时性标号）
——从始点到该标号点的最短路权上界
（4） 计算步骤及例子：
第一步：给起始点v1标上固定标号 , 其余各点标临时性标号 T(vj)=, j1;
= l1j
第二步：考虑满足如下条件的所有点
①与 v1相邻的点，即 ;
② 具有T 标号，即 ， 为T 标号点集.
修改 的T标号为 ，并将结果仍记为T(vj)。
s
v
j
Î
若网络图中已无满足此条件的T标号点，停止计算。
令 , 然后将 的T 标号改成P 标号，转入第二步。此时，要注意将第二步中的 改为 。
例一、 用Dijkstra算法求下图从v1到v6的最短路。
v1
v2
v3
v4
v6
v5
3
5
2
2
4
2
4
2
1
解 （1）首先给v1以P标号，给其余所有点T标号。
（2）
例一、 用Dijkstra算法求下图从v1到v6的最短路。
v1
v2
v3
v4
v6
v5
3
5
2
2
4
2
4
2
1
（4）
v1
v2
v3
v4
v6
v5
3
5
2
2
4
2
4
2
1
（5）
（6）
反向追踪得v1到v6的最短路为：