单源最短路径两种方法

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

2、的基本思想是从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)

3、和(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单位的费用。因为mind(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至ijv4的任一条路P,如果不是(v1,v4),则必是先从

4、v11&(v1,v2)到达v2,或者沿(v1,v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4,所需要的总费用都不会比1小(因为所有wij>0)。因而推知d(v1,v4)=1,这样就可以使v4变成具P标号的点。(4)现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1,v2)、(v1,v3)到达v2,v3,需要的费用分别为6与3,而从v4出发沿(v4,v6)至U达v6所需的费用是d(v1,v4)+w46=1+10=11单位。因mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d(v

5、1,v1)+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1,v3),d(v1,v3)=3。这样又可以使点v3变成具P标号的点,如此重复这个过程，可以求出从v1到任一点的最短路。在下述的Dijstra方法具体步骤中，用巳T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个入值，算法终止时入(v)=m,表示在Vs到v的最短路上，v的前一个点是Vm如果入(v)=8,表示图G中不含从Vs至ijv的路；入(Vs)=0。Dijstra方法的具体步骤：(初始化i=0S0=Vs,P(Vs)=0入

6、(Vs)=0对每一个v<>Vs,令T(v)=+入(v)=+°0,k=s开始如果Si=V,算法终止，这时，每个vCSi,d(Vs,v)=P(v);否则转入考察每个使(Vk,vj)CE且vjSi的点vj。如果T(vj)>P(vk)+wkj,则把T(vj)修改为P(vk)+wkj,把入(vj)修改为k。令如果，则把的标号变为P标号，令，k=ji,i=i+1,转，否则终止，这时对每一个vCSi,d(vs,v)=P(v),而对每一个。在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。2、分支限界法算法从图G的源顶点s和空优先队列开

7、始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应

8、的树中的结点为根的子树剪去。3、 计算求解过程、算法实现（源代码实现相关功能）1、贪心算法#include<iostream>#include<stdlib.h>usingnamespacestd;#defineMAX1000000/充当"无穷大"#defineLENsizeof(structV_sub_S)#defineN5#defineNULL0ints;/输入的源点intDN;/记录最短路径intSN;/最短距离已确定的顶点集constintGNN=0,10,MAX,30,100,MAX,0,50,MAX,MAX,MAX,MAX,0,MAX,1

9、0,MAX,MAX,20,0,60,MAX,MAX,MAX,MAX,0;typedefstructV_sub_S/V-S链表intnum;structV_sub_S*next;structV_sub_S*create()structV_sub_S*head,*p1,*p2;intn=0;head=NULL;p1=(V_sub_S*)malloc(LEN);p1->num=s;head=p1;for(inti=0;i<N+1;i+)if(i!=s)+n;if(n=1)head=p1;elsep2->next=p1;p2=p1;pl=(V_sub_S*)malloc(LEN);p

10、1->num=i;p1->next=NULL;free(p1);returnhead;structV_sub_S*DelMin(V_sub_S*head,inti)/删除链表中值为i的结点V_sub_S*p1,*p2;p1=head;while(i!=p1->num&&p1->next!=NULL)p2=p1;p1=p1->next;p2->next=p1->next;returnhead;voidDijkstra(V_sub_S*head,ints)structV_sub_S*p;intmin;S0=s;for(inti=0;i<

11、;N;i+)Di=Gsi;for(inti=1;i<N;i+)p=head->next;min=p->num;while(p->next!=NULL)if(Dp->num>D(p->next)->num)min=(p->next)->num;p=p->next;)Si=min;head=DelMin(head,min);p=head->next;while(p!=NULL)if(Dp->num>Dmin+Gminp->num)Dp->num=Dmin+Gminp->num;)p=p->n

12、ext;)voidPrint(structV_sub_S*head)structV_sub_S*p;p=head->next;while(p!=NULL)if(Dp->num!=MAX)cout<<"D"<<p->num<<":"<<Dp->num<<endl;p=p->next;)elsecout<<"D"<<p->num<<":"<<"00"<

13、<endl;p=p->next;)intmain()structV_sub_S*head;cout<<"输入源点s(0到4之间):"cin>>s;head=create();Dijkstra(head,s);head=create();Print(head);system("pause");return0;)2、分支限界法#include<iostream>#include<queue>usingnamespacestd;#defineMAX9999#defineN60intn,distN,aN

14、N;classHeapNodepublic:inti,length;HeapNode()HeapNode(intii,intl)i=ii;length=l;booloperator<(constHeapNode&node)constreturnlength<node.length;voidshorest(intv)priority_queue<HeapNode>heap;HeapNodeenode(v,0);for(inti=1;i<=n;i+)disti=MAX;distv=0;while(1)for(intj=1;j<=n;j+)if(aenod

15、e.ij<MAX&&enode.length+aenode.ij<distj)distj=enode.length+aenode.ij;HeapNodenode(j,distj);heap.push(node);if(heap.empty()break;elseenode=heap.top();heap.pop();)intmain()(cin>>n;for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)(cin>>a皿;if(aij=-1)aij=MAX;)shorest(1);for(inti=2;i&l

16、t;n;i+)cout<<disti<<""cout<<distn<<endl;return0;)、运行结果(截图)F六的刘帙支限界法小J*1|回- 110-130100- 1-150-1-1- 1-1-1-11H- 1-12B-160rl-1-1T-118503fl60Processexiteduithreturnualut0Pressanykeytocontinue.4、 计算复杂性分析(时间、空间)求单源、无负权的最短路。时效性较好，时间复杂度为O(V*V+E),可以用优先队列进行优化，优化后时间复杂度变为0(v*lgn)。源点可达的话，O(V*lgV+E*lgV)=>O(E*lgV)。当是稀疏图的情况时，此时E=V*V/lgV,所以算法的时间复杂度可为O(VA2)。可以用优先队列进行优化，优化后时间复杂度变为0(v*lgn)。5、 算法改进Dijkstra算法的运行时间要低，但它要求所有边的权值非负。Dijkstra算法中设置了一个顶点集合S,从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的顶点uCV-S,并将u加入S中，对u的所有出边进行松弛。由于总是在V-S中选择“最近”的顶点插入集合S中，可以