最短路问题Dijkstra算法.ppt

最短路问题
最短路问题是网络理论中应用最广泛的问题之一.
许多优化问题可以使用这个模型．如设备更新、管道铺设、线路安排、厂区布局等.
我们曾介绍了最短路问题的动态规划解法，但某些最短路问题(如道路不能整齐分段者)构造动态规划方程比较困准、而图论方法则比较有效。
最短路问题：在一个赋权图G上，给定两个顶点u和 v，在所有连接顶点u和 v 的路中，寻找路长最短的路（称为u和 v最短路.）
u和 v最短路的路长也称为u和 v的距离-d(u,v).
有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路.
1
一、网络无负权的最短路
本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。
算法的基本思路基于以下原理：
若序列vs ,v1 ,…,vn是从vs到vn的最短路，
则序列vs ,v1 ,…,vn-1必为从vs到vn-1的最短路。
——Dijkstra算法
2
Dijkstra算法基本思想
Dijkstra算法的基本思想是从vs出发，逐步地向外探寻最短路，采用标号法。
执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路长（称为P标号），或者是从vs到该点的最短路长的上界（称为T标号）。
算法每一步都把某个顶点的T 标号改为P 标号， 当终点vt 得到 P 标号时，计算结束。最多n-1步。
3
计算实例：
求连接 vs、vt 的最短路.
0
-
-
∞
-
∞
P
T
-
∞
-
∞
-
∞
-
∞
开始，给vs以 P 标号，P(vs)=0,
其余各点给 T 标号 T(vi)=+∞.
2
2
7
4
1
4
7
3
1
5
5
5
vs
v2
v1
vt
v4
v5
v3
Step 1:
迭代 1
Dijkstra算法基本步骤：
4
0
-
-
∞
-
∞
-
∞
-
∞
-
∞
-
∞
若 vi 为刚得到 P 标号的点,考虑这样的点
vj : (vi ,vj)∈E 且vj 为 T 标号。
2
2
7
4
1
4
7
3
1
5
5
5
vs
v2
v1
vt
v4
v5
v3
Step 2:
对vj的T 标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]
2
4
5
迭代 1
考察vs ,
T(v2)=min[T(v2),P(vs)+ws2]= min[+∞,0+5]=5
T(v1)=min[T(v1),P(vs)+ws1]= min[+∞,0+2]=2
5
0
-
-
∞
-
∞
-
∞
-
∞
-
∞
-
∞
比较所有具有 T 标号的点，把最小者改为P 标号，
2
2
7
4
1
4
7
3
1
5
5
5
vs
v2
v1
vt
v4
v5
v3
Step 3:
2
4
5
即 P(vi)=min[T(vi)].
当存在两个以上最小者时,可同时改为P 标号。若全部点为P标号,则停止。否则用vi代替vi转step 2.
-
2
迭代 1
全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs ,v1).
6
0
-
2
-
-
5
-
∞
-
∞
-
∞
-
4
2
2
7
4
1
4
7
3
1
5
5
5
vs
v2
v1
vt
v4
v5
v3
9
4
若 vi 为刚得到 P 标号的点,考虑这样的点
vj : (vi ,vj)∈E 且vj 为 T 标号。
Step 2:
对vj的T 标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]
迭代 2
考察v1 ,
T(v4)=min[T(v4),P(v1)+w14]= min[+∞,2+7]=9
T(v2)=min[T(v2),P(v1)+w12]= min[5,2+2]=4
7
0
-
2
-
-
4
-
9
-
∞
-
∞
-
4
2
2
7
4
1
4
7
3
1
5
5
5
vs
v2
v1
vt
v4
v5
v3
4
4
迭代 2
比较所有具有 T 标号的点，把最小者改为P 标号，
Step 3:
即 P