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

2006年全国信息学冬令营讲座第1页最短路算法及其应用广东北江中学余远铭【摘要】最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。【关键字】最短路【目录】一、基本概念....................................................................................21．1定义................................................................................................................................21．2简单变体.........................................................................................................................21．3负权边.............................................................................................................................31．4重要性质及松弛技术.....................................................................................................4二、常用算法....................................................................................52．1Dijkstra算法................................................................................................................52．2Bellman-Ford算法......................................................................................................72．3SPFA算法...................................................................................................................8三、应用举例..................................................................................103．1例题1——货币兑换...................................................................................................103．2例题2——双调路径....................................................................................................113．3例题3——Layout.......................................................................................................133．4例题4——网络提速...................................................................................................15四、总结..........................................................................................182006年全国信息学冬令营讲座第2页【正文】一、基本概念1．1定义乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是没必要考虑的。下面我们将阐明如何有效地解决这类问题。在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0,v1,……,vk)的权是指其组成边的所有权值之和：11()(,)kiiiwpwvv定义u到v间最短路径的权为min():)wpuvuvv如果存在由到的通路如果不存在从结点u到结点v的最短路径定义为权())wpv的任何路径。在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。1．2简单变体单目标最短路径问题：找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。单对结点间的最短路径问题：对于某给定结点u和v，找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。2006年全国信息学冬令营讲座第3页1．3负权边在某些单源最短路问题中，可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路，则对所有svV，最短路径的权的定义(,)sv依然正确。即使它是一个负值也是如此。但如果存在一从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径，因此如果从s到v的某路径中存在一负权回路，我们定义(,)sv。图1含有负权和负权回路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在一条路径(路径s,a)，所以：(,)(,)3sawsa。类似地，从s到b也只有一条通路，所以：(,)(,)(,)3(4)1sbwsawab。从s到c则存在无数条路径：s,c,s,c,d,c,s,c,d,c,c,d,c等等。因为回路c,d,c的权为6+(-3)=30，所以从s到c的最短路径为s,c，其权为：(,)5sc。类似地，从s到d的最短路径为s,c,d，其权为：(,)(,)(,)11sdwscwcd。同样，从s到e存在无数条路径：s,e,s,e,f,e,s,e,f,e,f,e等等.由于回路e,f,e的权为3+(-6)=-30，所以从s到e没有最短路径。只要穿越负权回路任意次，我们就可以发现从s到e的路径可以有任意小的负权值，所以：(,)se类似地，(,)sf因为g是从f可达的结点，我们从s到g的路径可以有任意小的负权值，则：2006年全国信息学冬令营讲座第4页(,)sg。结点h，j，i也形成一权值为负的回路，但因为它们从s不可达，因此(,)(,)(,)shsisj。一些最短路径的算法，例如Dijkstra算法，都假定输入图中所有边的权取非负数，如公路地图实例。另外一些最短路算法，如Bellman-Ford算法，允许输入图中存在权为负的边，只要不存在从源点可达的权为负的回路，这些算法都能给出正确的解答。特定地说，如果存在这样一个权为负的回路，这些算法可以检测出这种回路的存在。1．4重要性质及松弛技术本文的算法所运用的主要技术是松弛技术，它反复减小每个结点的实际最短路径的权的上限，直到该上限等于最短路径的权。让我们看看如何运用松弛技术并正式证明它的一些特性。定理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的最短路径矛盾。（证毕）下面看定理1的一个推论，它给出了最短路径的一个简单而实用的性质：推论1.1给定有向加权图G=(V,E),源点为s，则对于所有边(u,v)E，有(,)(,)(,)svsuwuv证明：从源点s到结点v的最短路径P的权不大于从s到v的其它路径的权。特别地，路径P的权也不大于某特定路径的权，该特定路径为从s到u的最短路径加上边(u,v)。（证毕）下面介绍松弛技术。对每个结点vV，我们设置一属性d[v]来描述从源s到v的最短路径的权的上界，称之为最短路径估计。我们通过下面的过程对最短路径估计和先辈初始化。经过初始化以后,对所有vV，[v]=NIL，对v=s，d[v]=0，对vV-{s}，INITIALIZE-SINGLE-SOURCE(G,s)1.For每个结点vV[G]2.Dod[v]3.[v]NIL4.d[s]02006年全国信息学冬令营讲座第5页d[v]=。松弛一条边(u,v)的过程包括测试我们是否可能通过结点u对目前找出的到v的最短路径进行改进，如果可能则更新d[v]和[v]，一次松弛操作可以减小最短路径的估计值d[v]并更新v的先辈域[v]，下面的代码实现了对边(u,v)的进一步松弛操作。图2对边(u,v)进行松弛图2说明了松弛一条边的两个实例，在其中一个例子中最短路径估计减小，而在另一实例中最短路径估计不变。(a)因为在进行松弛以前d[v]d[u]+w[u,v]，所以d[v]的值减小。(b)因为松弛前d[v]=d[u]+w[u,v]，所以松弛不改变d[v]得值。下文介绍的每个算法都调用INITIALIZE-SINGLE-SOURCE，然后重复对边进行松弛的过程RELAX。区别在于对每条边进行松弛操作的次数以及对边执行操作的次序有所不同。需要指出的是，松弛是改变最短路径估计和先辈的唯一方式。二、常用算法这一节着重讨论两种常用算法：Dijkstra算法和Bellman-Ford算法。虽然它们都是建立在松弛技术基础上的算法，但是在实现上有着各自的特点，适用的范围也有所不同。另外，我们还将介绍一种期望复杂度与边数同阶的高效算法——SPFA算法，并对其复杂度作出简要的分析。2．1Dijkstr