算法合集之《最短路算法及其应用》.ppt

最短路算法及其应用广东北江中学余远铭 yyming@ 最短路问题是图论中的核心问题之一, 它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离,如何找出这一最短行程? 一个在生活中常见的例子是: 一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线! 实际上,其中绝大多数路线我们是没必要考虑的。这时候,我们应该用一种系统的方法来解决问题,而不是通常人们所用的凑的方法和凭经验的方法。定义在最短路问题中,给出的是一有向加权图 G=(V,E) ,在其上定义的加权函数 W:E →R为从边到实型权值的映射。路径 P=(v0, v1, ……, vk) 的权是指其组成边的所有权值之和: 1 1 ( ) ( , ) k i i i w p w v v ????定义 u到v间最短路径的权为: ???? min ( ): ) w p u v u v v ? ??? ? ?? 如果存在由到的通路 如果不存在从结点 u到结点 v的最短路径定义为权的任何路径。( ) ) w p 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 s u wu v ? ?? ??证明: 从源点 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.