完整版最短路径算法附应用VIP专享VIP免费

1 / 16 最短路径算法及应用乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法就是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。那么我们很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是不值得考虑的。在这一章中， 我们将阐明如何有效地解决这类问题。在最短路径问题中，给出的是一有向加权图 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于 1959年提出来的。例 1 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1 出发，通过这个交通网到v8 去，求使总费用最小的旅行路线。Dijkstra方法的基本思想是从vs 出发，逐步地向外探寻最短路。执行过程中，与每个2 / 16 点对应，记录下一个数( 称为这个点的标号) ，它或者表示从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...