(完整word版)最短路径算法附应用

1、最短路径算法及应用乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。 如果有一张地图并在图上标 出每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法就是枚举出所有路径， 并计算出每条路径的长度， 然后选择最短的一条。 那么我们很容易看到， 即使不考虑包含回路的路径， 依然存在数以百万计的行车路线， 而其 中绝大多数是不值得考虑的。在这一章中， 我们将阐明如何有效地解决这类问题。 在最短路径问题中， 给出的是一有 向加权图 G（ V，E，W），其中 V为顶点集， E为有向边集， W为边上的权集。最短路径问 题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。一、 单

2、源最短路径问题所谓单源最短路径问题是指： 已知图 G（V，E），我们希望找出从某给定的源结点 SV 到 V 中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是 G中从 vs 到 vj 的最短路， vi 是 P 中的一个点，那么，从 vs 沿 P 到 vi 的路是从 vs 到 vi 的最短路。（一）Dijkstra 算法对于图 G，如果所有 Wij 0的情形下，目前公认的最好的方法是由Dijkstra 于 1959年提出来的。例 1 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费 用，现在某人要从 v1出发，通过这个交通网到 v8 去，求使总费用最小的旅行

3、路线。Dijkstra 方法的基本思想是从 vs 出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数 ( 称为这个点的标号 ) ，它或者表示从 vs 到该点的最短路的权 (称为 P 标号) 、或者是从 vs到该点的最短路的权的上界 (称为 T标号) ，方法的每一步是去修改 T 标号，并且把某一个具 T标号的改变为具 P标号的点，从而使 G中具 P 标号的顶点数多一个， 这样至多经过 n-1(n 为图 G的顶点数 ) 步，就可以求出从 vs 到各点的最短路。在叙述 Dijkstra 方法的具体步骤之前，以例 1 为例说明一下这个方法的基本思想。例 1 中， s=1。因为所有 Wi

4、j 0，故有 d(v1, v1)=0 。这时， v1 是具 P 标号的点。现在考察从 v1发出的三条弧， (v1, v2), (v1, v3)和(v1, v4) 。如果某人从 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)+w

5、14=1，可以断言，他从 v1到 v4所需要的最小费用必定是 1单位，即从 v1到v4的最短路是 (v1, v4)， d(v1, v4)=1 。这是因为从 v1 到 v4 的任一条路 P，如果不是 (v1, v4) ，则必是先从 v1 沿 (v1, v2)到达 v2，或者沿 (v1, v3)到达 v3。但如上所说，这时他已需要 6单位或 3单位的费用 ， 不管他如何再从 v2 或从 v3 到达 v4，所需要的总费用都不会比 1 小( 因为所有 wij 0)。因 而推知 d(v1, v4)=1 ，这样就可以使 v4 变成具 P 标号的点。现在考察从 v1 及 v4 指向其余 点的弧，由上已知，从

6、 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(v1, v4)+w46= d(v1, v1)+w13=3。基于同样的理由可以断言，从 v1到 v3 的最短路是 (v1, v3) ，d(v1, v3)=3 。这样又可以使点 v3 变成具 P 标号的点，如此重复这个过程，可以求出从 v1 到任一点的最短路。在下述的 Dijstra 方法具体

7、步骤中，用 P， T分别表示某个点的 P标号、 T标号， si 表 示第 i 步时，具P标号点的集合。 为了在求出从 vs 到各点的距离的同时， 也求出从 Vs到各 点的最短路，给每个点 v 以一个 值，算法终止时 (v)=m ，表示在 Vs到v 的最短路上， v 的前一个点是 Vm；如果 (v)= ，表示图 G中不含从 Vs 到 v 的路； (Vs)=0 。 Dijstra 方法的具体步骤： 初始化 i=0S0=Vs ，P(Vs)=0 (Vs)=0对每一个 v<>Vs，令 T(v)=+ ， (v)=+ ， k=s 开始 如果 Si=V ，算法终止，这时，每个 vSi， d(Vs,

8、v)=P(v) ；否则转入 考察每个使 (Vk,vj) E 且 vj Si 的点 vj 。如果 T(vj)>P(vk)+wkj ，则把 T(vj) 修改为 P(vk)+wkj ，把 (vj) 修改为 k。令如果，则把的标号变为P标号，令，k=ji ， i=i+1，转，否则终止，这时对每一个vSi， d(vs,v)=P(v) ，而对每一个算法实现：1、 数据结构 用邻接矩阵表示图 G 用一维数组 DI 存放从源点到 I 点的最短路径长度或其上界。（上面算法中的P标号与 T 标号实际上存放着源点到某点的最短路径长度或其上界，因此我们可以统一用D数组来表示）。 用一维数组 P，其中 PI 记录

9、到 I 点的最短路径中前一个顶点的序号。 $R+2、源程序9 / 16(二) Bellman-Ford 算法在单源最短路径问题的某些实例中，可能存在权为负的边。如果图G(V， E)不包含从源 s 可达的负权回路，则对所有 vV，最短路径的权定义 d(s,v) 依然正确，即使它是一 个负值也是如此。但如果存在一从 s 可达的负回路，最短路径的权的定义就不能成立。 S 到 该回路上的结点就不存在最短路径。当有向图中出现负权时，则 Dijkstra 算法失效。当不 存在源 s 可达的负回路时，我们可用 Bellman-Ford 算法实现。下面我们介绍有向图中，存在具有负权的弧时，求最短路的方法。为了

10、方便起见，不妨设从任一点 vi 到任一点 vj 都有一条弧(如果在 Gk ,(vi,vj) 不存 在，则添加 (vi,vj) 且令 wij=+ )。显然，从 vs 到 vj 的最短路总是从 vs 出发，沿着一条路到某个点 vi ，再沿 (vi,vj) 到 vj 的(这里 vi 可以是 vs 本身)，由本章开始时介绍的一个结论可知，从 vs 到 vi 的这条 路必定是从 vs 到 vi 的最短路，所以 d(vs,vi) 必满足如下方程：为了求得这个方程的解（这里 P 为图 G中的顶点数目），可用如下递推公式：开始时，令对 t=2,3,.,若进行到某一步，例如第 k 步时，对所有 j=1,2,.,

11、p,有：则 即为 vs 到各点的最短路的权。不难证明：（1）如果 G是不含回路的赋权有向图，那么， 从 vs 到任一个点的最短路必可取为初等 路，从而最多包含 P 2 个中间点；（ 2）上述递推公式中的是在至多包含 t-1 个中间点的限制条件下，从 vs到 vj 的最短路的权。由（1）（ 2）可知：当 G中不含负回路时，上述算法最多经过 p-1 次迭代必定收敛，即对所有的 j=1,2,.,P, 均有 ，从而求出从 vs 到各个顶点的最 短路的权。如果经过 p-1 次迭代，存在某个 j ，使，则说明 G中包含有负回路。显然，这时从 vs 到 vj 的路是没有下界的。根据以上分析， Bellman

12、-Ford 算法可描述为：算法实现1、 数据结构（同 Dijkstra 算法，略）2、源程序(三) 有向无回路图中的单源最短路径若图 G是一个无回路有向图，求图 G的单源最短路径问题可以在 O(V+E)时间内计算出 单源最短路径。在有向无回路图中最短路径总是存在的，这是因为即使图中有权为负的边， 也不可能存在权为负的回路。算法开始时先对有向无回路图进行拓朴排序，以便获得结点的线性序列。如果从结点 u 到结点 v 存在一通路，则在拓扑序列中 u 先于 v 。在拓扑排序过程中我们仅对结点执行一趟 操作。当对每个结点进行处理时，从该结点出发的所有边也被松驰。算法描述如下：二、每对结点间的最短路径我们

13、要讨论找出图中每对结点间最短路径问题。这个问题在实践中常常会出现。例如， 对一公路图，要造表说明其上的每对城市间的距离时就可能出现这种问题。对于有向图 G（V， E， W），要求每对结点间的最短路径，我们可以把单源最短路径算 法运行 V次来解决，每次依序把图中的每个结点作为源点。如果所有边的权为非负，可 以采用 Dijkstra 算法，算法的运行时间为 O（ V3）；如果允许有负权边的存在，我们必须 对每个结点运行一次速度较慢的 Bellman-Ford 算法，其中运行时间为 O（ V2E），对稠密图 则为 O（ V4）。下面我们介绍一种动态程序设计方案来解决可以存在负权边但无负回路的有向图G

14、（V， E），每对结点间的最短路径问题，所产生的算法称为Floyd-Warshall 算法，其运行时间为 O（V3）。（一）最短路径的结构在 Floyd-Warshall 算法中，考察的是一条最短路径上的"中间 "结点，其中某条简单路径 P=<V1,V2,.,Vj> 的中间结点是 P中除 V1和 Vj 以外的任何结点，即任何属于集合 V2,V3.,Vj 1的结点。该算法主要基于下列观察。设 G的结点为 V 1,2,.,n ，并对某个 k 考察其结点 子集 1,2 ， .,k 。对任意一对结点 i,j V，考察从 i 到 j 且其中间结点皆属于集合 1,2 ，.,

15、k 的所有路径，设 P 是其中一条最小权路径 （因为我们假定 G中不包含负权回 路，所以 P 是简单路径） 。Floyd-Warshall 算法利用了路径 P与从 i 到 j 间的最短路径 （所 有中间结点皆属于集合 1,2 ，.,k-1 之间的联系。这一联系取决于 k 是否是路径 p 的一 个中间结点。如果 k是路径 p的中间结点，由如下图所示，我们把p分解为 p1（i k）,p2（k j ）。由前面可知， p1是从 i 到 k的一条最短路径， 且其所有中间结构均属于集合 1,2 ，.,k 。事实上，结点 k不是路径 p1的中间结点， 所以 p1是从 i 到 k的一条最短路径， 且满足 所有

16、中间结点均属于 1,2 ，.,k-1 。类似地， p2 是从 k 到 j 的一条最短路径，且其中 间结点皆属于集合 1,2 ， .,k-1 。二）解决每对结点间最短路径问题的一种递归方案基于上述观察，我们将给出定义最短路径估计的一个递归公式。设 为从结点 i 到 结点 j 且满足所有中间均属于集合 1,2 ，.,k 的一条最短路径的权。当 k=0 时，从结点 i 到结点 j 的路径中根本不存在中间结点， 因此它至多包含一条边， 则有 ，递归 定义由下式给出：矩阵给出了最后解， 对所有的 i,j V成立因为其所有中间点皆属于 1,2 ，.,n 。三）自底向上计算最短路径的权基于以上给出的递归定义

17、，我们可以运用下面自底向上过程按 k 值的递增顺序计算n*n 的矩阵 W。其返回值关于最短路径的权的矩阵。( 四 ) 建立最短路径有时除了需要计算出一个带权的有向图中从任一顶点到其他顶点之间的最短路径的长 度外，还要确定相应的最短路径。为此，可以设置一个 n*n 的矩阵 P，当 k 是在 Floyd 算法 中，使 Dij 达到最小值时， 就置 Pi,j=k 。约定 Pi,j=0, 表示从顶点 i 顶点 j 的最短路径 就是从 i 到 j 的边。下面是修改后的 Floyd 算法，其中包含了计算矩阵矩阵 P 的步骤。根据矩阵 P，要计算出顶点 i 到 j 的最短路径可以由以下过程 Path(i,j

18、) 实现： Procedure Path(i,j:integer);Var k:integer;BeginK:=Pi,j;If k=0 then return;Path(i,k);Print(k);Path(k,j);End;(五) 源程序di j ：= d.tk+d j;Pij<jj=k;End;End;PrOCedUre Fath(i, j:integer)JVar k：integer;BegIrLK:=Pi, j;If k=0 then exit;Path(i,k);Write (f,k->j);Path,j);End,ProCedUre init;VaT f:text;i,

19、 jj tl XJ y1 Wn： integer;beginassign Cf,' JIllniroadr ad. inl,);xeet (f);readln(f t t., Wil);for i:=1 to n dofor j：=l to n doijf i=j then wi.4 j ： =O else w, j MaXint;for i： =1 t Im doXeadln(f, XJ y, W x., y);ClOSe (f);end;begininit;f lyd(d., w);assign (f», inroadroad OUtJ);rewrite (Jf);for

20、 i：=l to n dofor j:=1 to n doif (i<>j)and(di,1 j OMaxint) thenbeginWrIteIn(f/Path , j j j todi .j);Wllte (f,4 i, _>j ); PathCiI J) ;writeln Cf, J);end;readln;CIoSe Cf);end.三、应用举例1、设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置 新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备， 则需支付一定的维修费用。 现在的问题是如何制定一个几年之内的设备更新计划， 使得总的 支付费用最少。例如，我们一个五年之内要更新某种设备的计划，若已知该种设备在各年年初的价格为：第一年第二年第三年第四年第五年1111121213还已知使用不同时间（年）的设备所需要的维修费用为：使用年数0112233445维修费用5681118可供选择的设备更新方案显然很多的， 例如， 每年都购置