文档介绍：最短路径算法及应用
乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？
一种可能的方法就是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。那么我们很容易看到，即使不考虑包含回路的路径,依然存在数以百万计的行车路线，而其中绝大多数是不值得考虑的.
在这一章中，我们将阐明如何有效地解决这类问题。在最短路径问题中,给出的是一有向加权图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出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号），它或者表示从vs到该点的最短路的权(称为P标号）、或者是从vs到该点的最短路的权的上界(称为T标号),方法的每一步是去修改T标号，并且把某一个具T标号的改变为具P标号的点,从而使G中具P标号的顶点数多一个,这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。
在叙述Dijkstra方法的具体步骤之前，，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={ d（v1， v1)+w12,d(v1， v1）+w13，d（v1, v4）+w46｝= d（v1， v1）+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1， v3），d（v1, v3)=，如此重复这个过程，可以求出从v1到任一点的最短路。
在下述的Dijstra方法具体步骤中,用P，T分别表示某个点的P标号、T标号，si表示第i步时，,也求出从Vs到各点的最短路，给每个点v以一个λ值，算法终止时λ(v)=m，表示在Vs到v的最短路上,v的前一个点是Vm；如果λ（v)=∞，表示图G中不含从Vs到v的路；λ（Vs）=0。
Dijstra方法的具体步骤：
{初始化｝
i=0
S0={Vs｝，P（Vs）=0 λ(Vs)=0
对每一个v〈>Vs，令T（v）=+ ∞,λ(v）=+ ∞,
k=s
｛开始｝
①如果Si=V，算法终止，这时，每个v∈Si，d（Vs,v)=P(v)；否则转入②