文档介绍：最短路算法及其应用
广东北江中学余远铭
yyming@
最短路问题是图论中的核心问题之一,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。
乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离,如何找出这一最短行程?
一个在生活中常见的例子是:
一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。
然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线!
实际上,其中绝大多数路线我们是没必要考虑的。
这时候,我们应该用一种系统的方法来解决问题,而不是通常人们所用的凑的方法和凭经验的方法。
定义
在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权函数W:E→R为从边到实型权值的映射。路径P=(v0, v1,……, vk)的权是指其组成边的所有权值之和:
定义u到v间最短路径的权为:
从结点u到结点v的最短路径定义为权的任何路径。
在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。
边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。
重要性质
定理1 (最优子结构) 给定有向加权图G=(V,E),设P=<v1, v2,…, vk>为从结点v1到结点vk的一条最短路径,对任意i,j有i<=j<=k,设Pij=< vi, vi+1,…, vj>为从vi到vj的P的子路径,则Pij是从vi到vj的一条最短路径。
证明:我们把路径P分解为<v1,v2,…,vi,vi+1,…vj,…vk>。则w(P)=w(P1i)+w(Pij)+w(Pjk)。现在假设从vi到vj存在一路径P’ij,且w(P’ij)<w(Pij),则将P中的路径Pij=(vi,vi+1,…vj)替换成P’ij,依然是从v1到vk的一条路径,且其权值 w(P1i)+w(P’ij)+w(Pjk)小于w(P),这与前提P是从v1到vk的最短路径矛盾。(证毕)
推论
给定有向加权图G=(V,E),源点为s,则对于所有边(u,v) E,有:
证明: 从源点s到结点v的最短路径P的权不大于从s到v的其它路径的权。特别地,路径P的权也不大于某特定路径的权,该特定路径为从s到u的最短路径加上边(u,v)。(证毕)
松弛技术
INITIALIZE-SINGLE-SOURCE(G,s)
1. For 每个结点 v V[G]
2. Do d[v] ←
3. [v] ← NIL
4. d[s] 0
对每个结点v V,我们设置一属性d[v]来描述从源s到v的最短路径的权的上界,称之为最短路径估计。我们通过下面的过程对最短路径估计和先辈初始化。
RELAX(u,v,w)
1. If d[v] > d[u] + w(u,v)
2. Then d[v] ← d[u] + w(u,v)
3. [v] ← u
一次松弛操作可以减小最短路径的估计值d[v]并更新v的先辈域[v]
常用算法
一、Dijkstra算法
二、Bellman-Ford算法
三、SPFA算法
Dijkstra算法
Dijkstra算法中设置了一结点集合S,从源结点s到集合S中结点的最终最短路径的权均已确定,即对所有结点v S,有d[v]= (s,v)。算法反复挑选出其最短路径估计为最小的结点u V-S,把u插入集合S中,并对离开u的所有边进行松弛。
Dijkstra(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,S)
2. S
3. Q ← V[G]
4. While Q
5. Do u ← EXTRACT-MIN(Q)
6. S ← S U {u}
7. For 每个顶点v Adj[u]
8. Do RELAX(u,v,w)