文档介绍：最短路问题
赵嘉诚
Dijkstra算法
Ford算法
Floyd算法
SPFA算法
一、什么是最短路问题
例下图为单行线交通网,每弧旁的数字表示通过这条
线所需的费用。现在某人要从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= ……
旅行路线总费用路上所有弧权之和。
最短路问题中,不考虑有向环、并行弧。
即适用于DAG(有向无环图)
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中的两个顶点A,B。设P是D中从A到B的一条路,定义路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的最短路。
最短路的子路也是最短路。
Dijkstra算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
思想:将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一定只有一条弧。
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
∞
∞
1
∞
∞
∞
3