最短路问题dijkstra floyd 算法.ppt

最短路问题
最短路问题
Dijkstra算法
Ford算法
Floyd算法
一、最短路问题
例下图为单行线交通网,每弧旁的数字表示通过这条
线所需的费用。现在某人要从v1出发,通过这个交
通网到v8去,求使总费用最小的旅行路线。
v2
v5
2
3
4
6
4
v3
v1
v4
v6
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
从v1到v8:
P1=(v1,v2,v5,v8) 费用 6+1+6=13
P2=(v1,v3,v4, v6, v7, v8) 费用 3+2+10+2+4=21
P3= ……
从v1到v8的旅行路线从v1到v8的路。
旅行路线总费用路上所有弧权之和。
最短路问题中,不考虑有向环、并行弧。
v2
v5
2
3
4
6
4
v3
v1
v4
v6
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
最短路问题
给定有向网络D=(V,A,W),任意弧aij∈A,有权w( aij )=wij,给定D中的两个顶点vs,vt。设P是D中从vs到vt的一条路,定义路P的权(长度)是P中所有弧的权之和,记为w(P)。最短路问题就是要在所有从vs到vt的路中,求一条路P0 ,使
称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。
二、Dijkstra算法
当所有 wij ≥0 时,本算法是用来求给定点vs到任一个点vj 最短路的公认的最好方法。
事实:如果P是D中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到 vi的最短路。
最短路的子路也是最短路。
思想:将D=(V,A,W)中vs到所有其它顶点的最短
路按其路长从小到大排列为:
u0≤ u1 ≤ u2 ≤…≤ un
u0表示vs到自身的长度,相应最短路记为:
P0,P1,P2,…,Pn,
取最小值的点为v1, ∴P1=P(vs,v1)
假定 u0,u1,…,uk的值已求出,对应的最短路分别为
P1=P(vs,v1), P2=P(vs,v2),…, Pk=P(vs,vk)
P1一定只有一条弧。
记
则
使上式达到最小值的点v’可取为vk+1。
计算过程中可采用标号方法。
Xk中的点,ui 值是vs 到vi 的最短路长度,相应的点记“永久”标号;
XK中的点,ui值是vs到vi的最短路长度的上界,相应的点记“临时”标号,供进一步计算使用。
前点标号i : 表示点vs到vj的最短路上vj的前一点。
如i=m,表示vs到vj的最短路上vj前一点是vm。
1,6
图上标号法:
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
1, ∞
1, ∞
1,1
1, ∞
1, ∞
1, ∞
1,3
1,6
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
1, ∞
4,11
1,1
1, ∞
1, ∞
1, ∞
1,3
图上标号法: