文档介绍：最短路径算法及应用乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离,如何找出这一最短行程? 一种可能的方法就是枚举出所有路径, 并计算出每条路径的长度, 然后选择最短的一条。那么我们很容易看到, 即使不考虑包含回路的路径, 依然存在数以百万计的行车路线, 而其中绝大多数是不值得考虑的。在这一章中, 我们将阐明如何有效地解决这类问题。在最短路径问题中, 给出的是一有向加权图 G=(V,E,W), 其中 V 为顶点集,E 为有向边集,W 为边上的权集。最短路径问题研究的问题主要有:单源最短路径问题、与所有顶点对之间的最短路径问题。一、单源最短路径问题所谓单源最短路径问题是指: 已知图 G=(V,E), 我们希望找出从某给定的源结点 S∈V 到V 中的每个结点的最短路径。首先,我们可以发现有这样一个事实:如果 P是G 中从 vs到 vj 的最短路, vi是P中的一个点,那么,从 vs沿P到 vi 的路是从 vs到 vi 的最短路。(一) Dijkstra 算法对于图 G ,如果所有 Wij ≥0 的情形下,目前公认的最好的方法是由 Dijkstra 于 195 9 年提出来的。例1 已知如下图所示的单行线交通网,每弧旁的数字表示通过这条单行线所需要的费用,现在某人要从 v1 出发,通过这个交通网到 v8 去,求使总费用最小的旅行路线。 Dijkstra 方法的基本思想是从 vs 出发, 逐步地向外探寻最短路。执行过程中, 与每个点对应, 记录下一个数( 称为这个点的标号), 它或者表示从 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, 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)+w14=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 指向其余点的弧,由上已知,从 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 方法具体步骤中,用 P,T 分别表示某个点的 P 标号、 T 标号, si表示第 i 步时,具P 标号点的集合。为了在求出从 vs 到各点的距离的同时, 也求出从 Vs 到各点的最短路,给每个点 v 以一个λ值,算法终止时λ(v)=m ,表示在 Vs到v 的最短路上, v 的前一个点是 Vm ;如果λ(v)= ∞,表示图 G 中不含从 Vs到v 的路; λ(Vs)=0