《最短路径算法及应用》由会员分享，可在线阅读，更多相关《最短路径算法及应用（16页珍藏版）》请在金锄头文库上搜索。
1、最短路径算法及应用乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标 出每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法就是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。 那么我们很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而其 中绝大多数是不值得考虑的。在这一章中，我们将阐明如何有效地解决这类问题。在最短路径问题中，给出的是一有 向加权图G=（V, E，W）,其中V为顶点集，E为有向边集，W为边上的权集。最短路径问 题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。一、单源最短路径问题所谓单源最短
2、路径问题是指：已知图G= （V，E），我们希望找出从某给定的源结点SUV 到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中 的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。（一）Dijkstra 算法对于图G,如果所有Wij三0的情形下，目前公认的最好的方法是由Dijkstra于1959 年提出来的。例1已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费 用，现在某人要从vl出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v83v9Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。
3、执行过程中，与每个 点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P 标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T 标号，并且把某一个具T标号的改变为具P标号的点,从而使G中具P标号的顶点数多一个, 这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例 1中，s=1。因为所有Wij三0,故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从 v1发出的三条弧，(v1, v2), (v1, v3)和(v1, v
4、4)。如果某人从v1出发沿(v1, v2)到达v2, 这时需要d(v1, v1)+w12=6单位的费用；如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用；类似地，若沿(v1, v4)到达v4,这时需要d(v1, v1)+w14=1单位的 费用。因为 min d(v1, v1)+w12, d(v1, v1)+w13, d(v1, v1)+w14= d(v1, v1)+w14=1, 可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4), d(v1, v4)=1。这是因为从v1到v4的任一条路P,如果不是(v1,
5、v4),则必是先从v1沿(v1, v2)到达v2,或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用， 不管他如何再从v2或从v3到达v4,所需要的总费用都不会比1小(因为所有wij20)。因 而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。现在考察从v1及v4指向其余 点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3,需要的费用分别 为6与3,而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因 min d(v1, v1)+w12, d(v1, v1)+w13, d
6、(v1, v4)+w46= d(v1, v1)+w13=3o 基于同样的理 由可以断言，从v1到v3的最短路是(v1, v3), d(v1, v3)=3。这样又可以使点v3变成具P 标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。在下述的Dijstra方法具体步骤中，用P, T分别表示某个点的P标号、T标号，si表 示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各 点的最短路，给每个点v以一个入值，算法终止时入(v)=m，表示在Vs到v的最短路上， v的前一个点是Vm；如果入(v)=8，表示图G中不含从Vs到v的路；入(Vs)=0。 Dijstra
7、方法的具体步骤：初始化i=0S0=Vs, P(Vs)=0 入(Vs)=0对每一个 vVs，令 T(v)=+ ,入(v)=+ ,k=s 开始 如果Si=V，算法终止，这时，每个veSi, d(Vs,v)=P(v)；否则转入 考察每个使(Vk,vj)eE且vj Si的点vj。如果 T(vj)P(vk)+wkj,则把 T(vj)修改为 P(vk)+wkj,把入(vj)修改为 k。=吧) 令ZT(y7-) +coy.P t V ) = 7(v.)如果 7丿 ，则把的标号变为P标号 ，令,k=ji, i=i+1,转，否则终止，这时对每一个vesi, d(vs,v)=P(v),而对每算法实现:1、数据结构
8、卡用邻接矩阵表示图G* 用一维数组DI存放从源点到I点的最短路径长度或其上界。（上面算法中的P 标号与T标号实际上存放着源点到某点的最短路径长度或其上界，因此我们可以统一用D 数组来表示）。* 用一维数组P,其中PI记录到I点的最短路径中前一个顶点的序号。$R+2、源程序Program Min_Road_Dijkstra;Const MaxN=100;Type GraphType=Array1. . MaxNj 1. . MaxN of integer;有向图邻接袒阵Varw:GraphType;图&结构? Wl, j表乔顶点.i到j之间的费用s., n:integer;h为源点.，n为图G的
9、顶点_数存敗从源点到任意顶点之间的最短路径长度或其上界D:array1.MaxNofinteger;SS:array 1.MasN ofboolean;标有 F 标号的顶点集合pi存飲最短路中顶点.1的前面顶点编号p:array1.Masnofinteger;Procedure Init; 文件输入过程，读入图信息、var f :test;k, y, nw, i, j： integer;beginassign(f., miniroadRoad. in);reset (f);r e adln (f, n, s_, nw);for i：=l to n dofor j：=1 to n do wi.,
10、 j ：=Maxint;for i：=l to nw doreadln (f_, k, y_, w k., y);close (f);end;Procedure Dijkstra; Di jkstra 算法过程var miiij k., i, j, tempk： integer;beginfillchar(SSj sizeof(SS)j 0);始化SS s ：=true;ps ：=0; 源点标上 F 标号for i：=l to n doif is then D i ：=ws., i;Ds:二0;k：=s;min：=-l;：i=l=l=l=l=i=i=l=l=l=i=i=l=l=l=i=i=l=
11、l=l=l=i=i=l=l=l4 while minOMaxint己口 当存在所有T标号点.的距离上畀的最小值 beginmin：=MaKint;for j ： = 1 to n do begin在所有 T标号点进行操作如果J未标P标号，且到J的路径长度上界可更新，则更新为鞍小值 if (not ss j) and(wk., j OMaxint) and(dj D k-hirk, j) then begin Dj：=D k-hrk, .;pjl ：=k;end;寻找最小具有T标号的距离最小点.if (not ssj)and(Djmin) then beginmin：=Dj;TempK：=j;e
12、nd;end;if minMaxint then begin 如果找到，则该点.标上P标号k：=tempk;ss k：=true;end;end;end;Procedure Print; 打印出路径var i, j:integer;temps., temppath： string;beginfor i：=l to n doif is thenif D i=Maxint then 如果D二Maxiirt,则输出无路径到该点.wiiteln (s_,J ToJ 3 ijJ have no path/ )else begin 否则从该点倒着输出从源点到该点的路径wiitelnfsj3 To 3,1/
13、 Cost / D i);temppath：;str(i, temps);temppath：=J +temps+temppath;J：=pi；while j0 do beginstr(j, temps);temppath：=J-一+t emp s+t empp ath;J：二pj；end;str (s_, temps);t empp ath:二 t emp s+t empp ath;wiiteln(temppath);end;end;begin 主程序init;Dijkstra;print;end.(二) Bellman-Ford 算法在单源最短路径问题的某些实例中，可能存在权为负的边。如果图
14、G=(V, E)不包含 从源s可达的负权回路，则对所有vUV,最短路径的权定义d(s,v)依然正确，即使它是一 个负值也是如此。但如果存在一从s可达的负回路，最短路径的权的定义就不能成立。S到 该回路上的结点就不存在最短路径。当有向图中出现负权时，则Dijkstra算法失效。当不 存在源s可达的负回路时，我们可用Bellman-Ford算法实现。下面我们介绍有向图中，存在具有负权的弧时，求最短路的方法。为了方便起见，不妨设从任一点vi到任一点vj都有一条弧(如果在Gk ,(vi,vj)不存 在，则添加(vi,vj)且令wij=+*)。显然，从vs到vj的最短路总是从vs出发，沿着一条路到某个点
15、vi,再沿(vi,vj)到 vj的(这里vi可以是vs本身)，由本章开始时介绍的一个结论可知，从vs到vi的这条 路必定是从vs到vi的最短路，所以d(vs,vi)必满足如下方程：皿叫七J =吨個(比宀)+叫为了求得这个方程的解说耳“），捡宀），皿（叫丹）（这里p为图g中的顶点数 目），可用如下递推公式：开始时，令护他舟）=叫 （j = 12加对t=2,3, ,沙他丹）=nm個宀亿皿）+叫0= 12申）若进行到某一步，例如第k步时，对所有j=l,2,.，p，有：尹条宀）宀）则小叽七即为vs到各点的最短路的权。不难证明：（1）如果G是不含回路的赋权有向图，那么，从vs到任一个点的最短路必可取为初等 路，从而最多包含P-2个中间点；疔（V V）（2
