最短路算法及其应用.doc

最短路算法及其应用.doc:..最短路算法及其应用【摘要】最短路问题是图论中的核心问题0—,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看耳最短路问题没冇什么关系,却也可以归结为最矩路问题。木文较详尽地介绍了相关的基木概念、常用算法及英适用范围,并对其应用做出了举例说明,侧重于模型的建立、思考和证明的过程,最后作出总结。【关键字】最短路【H录】一、 基木概念 11- 1定义 3二、常用算法 -Ford算法 6三、 应用举例 ——双调路径 Layout 83. 4例题4——网络提速 10四、总结 12【正文】一、。如果有一张地图并在地图上标出了每对十字路UZ间的距离,如何找出这一最短行程?一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线,而其中绝大多数是没必要考虑的。下面我们将阐明如何有效地解决这类问题。在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权苗数W:ETR为从边到实型权值的映射。路径P二(v。,m••••••,vj的权是指其组成边的所有权值之和:ki=\定义u到V间最短路径的权为V)=min{w(p):u—>v}如果存在由u到卩的通路g 如果不存在从结点"到结点y的最短路径定义为权vv(p)=力(3叭的任何路径。在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的H标是从起点出发找一条到达H的地的最短路径。边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用來表示时间、金钱、罚款、损失或任何英他沿路径线性积累的数量形式。:找出从每一结点y到某指定结点"的一条最短路径。把图屮的每条边反向,我们就可以把这一问题转化为单源最矩路径问题。单对结点间的最短路径问题:对于某给定结点“和*找岀从〃到y的一条故短路径。如果我们解决了源结点为〃的单源问题,则这一问题也就获得了解决。对于该问题的最坏情况,从渐进意义上看,目前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题:对于每对结点"和r,找出从"到7的最短路径。我们可以用单源算法对每个结点作为源点运行-次就可以解决问题。,可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路,则对所冇VGVv,最短路径的权的定义V)依然正确。叩使它是一个负值也是如此。但如果存在一从s可达的负权冋路,最短路径的定义就不能成立了。从s到该冋路上的结点不存在最短路径一一因为我们总可以顺着找出的“故短”路径再穿过负权回路从而获得一权值更小的路径,因此如果从s到y的某路径小存在一负权回路,我们定义6(几V)=-oo0图1含有负权和负权冋路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在•条路径(路径<s,a>),所以:》(S,G)=VV(S,G)=3。类似地,从S到b也只冇一条通路,所以:—w(s,d)+w(Q,b)=3+(-4)=一1。从S到C则存在无数条路径:〈s,c〉,Cs,c,d,c>,<s,c,d,c,c,d,c獲等。因为回路C,d,C的权为6+(-3)二3〉0,所以从s到c的最短路径为〈s,c>,其权为:/(f,c)=5。类似地,从S到d的最短路径为Cs,c,d>,其权为:=w(s,c)+w(c,d)=ll。同样,从S到e存在无数条路径:<s,e〉,<s,e,f,e〉,〈s,e,f,e,f,•回路命/»的权为3+(-6)=-3<0,所以从s到e没有最短路径。只要穿越负权冋路任意次,我们就可以发现从s到e的路径可以有任意小的负权值,所以:/(£,幺)=-oo类似地,/(£,/)=-oo因为g是从/•可达的结点,我们从S到g的路径可以有任总小的负权值,则:结点h,j,i也形成一权值为负的回路,但因为它们从s不可达,因此5($,h)=/($,i)=J(5,y)=oo0一些最短路径的算法,例如Dijkstra算法,都假定输入图屮所有边的权取非负数,如公路地图实例。另外一些最短路算法,如Bellman-Ford^.允许输入图中存在权为负的边,只要不存在从源点可达的权为负的回路,这些算法都能给出正确的解答