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

《算法合集之《最短路算法及其应用》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、最短路算出及其应用广东北江中学余远铭【摘要】最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。【关键字】最短路【目录】一、基本概念21.1定义21.2简单变体21.3负权边31.4重要性质及松弛技术4二、常用算法52.1Dijkstra算法52.2Bellman-Ford算法72.3SPFA算法8三、应用举例103.1例题1货币兑换1

2、03.2例题2——双调路径113.3例题3——Layout133.4例题——网络提速15四、总结18【正文】1.1定义乘汽车旅行的人总希望找出到口的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们很容易看到，即使不考虑含凹路的路径，依然存在数以百万计的行车路线，而其中绝大多数是没必要考虑的。下面我们将阐明如何有效地解决这类问题。在最短路问题中，给出的是一冇向加权图G=(V,E),在其上定义的加权函数W:EtR为从边到实型权值的映射。路径P=(Vo,V1

3、5......,Vk)的权是指其组成边的所有权值Z和：1=1定义u到V间最短路径的权为min{w(p):w—>v}00如果存在由“到惦勺通路如果不存在从结点U到结点V的最短路径定义为权w(p)=5(u°)的任何路径。在乘车旅行的例了中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点岀发找一条到达目的地的最短路径。边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。1.2简单变体单目标最短路径问题：找出从每一结点V到某指定结点“的一条最短路径。把图

4、屮的每条边反向，我们就可以把这一问题转化为单源最短路径问题。单对结点间的:短路径问题:对于某给定结点U和V,找出从U到V的一条最短路径。如果我们解决了源结点为U的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，冃前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题：对于每对结点"和V,找岀从"到V的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。1.3负权边在某些单源最短路问题中，可能存在权为负的边。如果图G(V,E)不包含由源$可达的负权回路，则对所有veV.,最短路径的权的定义汉$°)依然正确。即使它是一个负值也是如此

5、。但如果存在一从$可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径，因此如果从s到卩的某路径小存在一负权回路，我们定义5(s,v)=-oo。图1含有负权和负权回路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点$到该结点的最短路径的权。因为从5到a只存在一条路径(路径,

6、,c,d,c>,等等。因为冋路的权为6+(・3)=3>0,所以从$到。的最短路径为<5,0,其权为：/($,c)=5o类似地，从S到d的最短路径为VS,C,d>,其权为：/(s,d)=w(s,c)+w(c,d)=11o同样，从s到e存在无数条路径：,,等等.由于冋路“/；£>的权为3+(-6)=-3<0,所以从s到e没有最短路径。只要穿越负权回路任意次，我们就可以发现从s到e的路径可以有任意小的负权值，所以：5(s,w)=-oo类似地，/($,/)=Y0因为g是从/可达的结点，我们从

7、5到g的路径可以有任意小的负权值，则:5（$,g）二-ooo结点h,j,i也形成一权值为负的冋路，但因为它们从s不可达，因此/（s,/z）=5（$」）=》“,））=ooo一些最短路径的算法，例如Dijkstra算法，都假定输入图中所有边的权取非负数，如公路地图实例。另外一些最短路算法，如Bellman-Ford算法，允许输入图中存在权为负的边，只要不存在从源点可达的权为负的冋路，这些算法都能给出正确的解答。特定地说，如果存在这样一个权为负的冋路，这些算法可以检测出这种回路的存在。