单源最短路径(两种方法).doc

《单源最短路径(两种方法).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.单源最短路径计科一班李振华20120407111、问题描述给定带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。2、问题分析推导过程（最优子结构证明，最优值递归定义）1、贪心算法对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发

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

3、本思想。s=1。因为所有Wij≥0，故有d(v1,v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1,v2),(v1,v3)和(v1,v4)。（1）如果某人从v1出发沿(v1,v2)到达v2，这时需要d(v1,v1)+w12=6单位的费用；（2）如果他从v1出发沿(v1,v3)到达v3，这时需要d(v1,v1)+w13=3单位的费用；（3）若沿(v1,v4)到达v4，这时需要d(v1,v1)+w14=1单位的费用。因为min{d(v1,v1)+w12，d(v1,v1)+w13，d(v1,v1)

4、+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标号的点。（4）现在考察从v1及v4指向其余点的

5、弧，由上已知，从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方法具体

6、步骤中，用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，算法终止，这时，每个v∈Si，d(Vs,v

7、)=P(v)；否则转入②②考察每个使(Vk,vj)∈E且vjSi的点vj。如果T(vj)>P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把λ(vj)修改为k。③令如果，则把的标号变为P标号，令，k=ji，i=i+1，转①，否则终止，这时对每一个v∈Si，d(vs,v)=P(v)，而对每一个。在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。2、分支限界法算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具

8、有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，