最短路径三种算法及比较-PASCAL

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最短路径三种算法及比较,by:JCR,导语,最短路无非就是那三种算法：,Floyd,Dijkstra,Spfa,这三种算法各有各的好处，我们一一介绍一下。,floyd,dijkstra,spfa,floyd,大意很简单，就是：,对于,A,B,两点他们之间的路径长为,la,b,如果存在一点,C,使得,la,bla,c+lb,c,则赋值,la,b=la,c+lb,c,因此，我们对,ABC,三点都要循环一次才能找到最小值，算法效率,O(N,3,),，速度太慢，但是好处就是容易打，不容易错，查错也方便。,floyd,程序,for k:=1 to p do for i:=1 to p do if ki then /,重复就没意义了,for j:=1 to p do if(ji)and(jk)then if bi,jbi,k+bk,j then/,如果有更短路,bi,j:=bi,k+bk,j;/,更新,Dijkstra,按路径长度递增次序产生最短路径算法：,把,V,分成两组：,（,1,）,S,：已求出最短路径的顶点的集合,（,2,）,V-S=T,：尚未确定最短路径的顶点集合,算法步骤如下：,1.,初使时令,S=V0,T=,其余顶点,，,T,中顶点对应的距离值,若存在,，,dV0,Vi,为,弧上的权值,若不存在,，,dV0,Vi,为,maxlongint,2.,从,T,中选取一个其距离值为最小的顶点,W,且不在,S,中，加入,S,3.,对,T,中顶点的距离值进行修改：若加进,W,作中间顶点，从,V0,到,Vi,的,距离值比不加,W,的路径要短，则修改此距离值,重复上述步骤,2,、,3,，直到,S,中包含所有顶点，即,S=T,为止,Dijkstra,代码,for i:=1 to l do ti:=10000;tfirst:=0;u:=first;fillchar(s,sizeof(s),0);sfirst:=true;for i:=1 to l-1 do beginforj:=1 to l do if not(sj)and(tu+au,jtj)thenbegin tj:=tu+au,j;end;min:=max;for j:=1 to l doif not(sj)and(tj,Dy+Ly,k,则,Dk,=,Dy+Ly,k,，如果,y,不在队列中则把,y,加入队列。,前提：,Y,与,S,是联通的，并且,y,与,k,是联通的，下面程序中避免了不联通的情况,spfa,procedure,spfa(s:longint,);,var,i,k:longint,;beginfillchar(d,sizeof(d),$7f);,如果是,maxlongint,，相加时会爆掉，这个数大概在,2,亿左右，不会爆，也比,maxint,好，因为有时数据可能会大过,32768,fillchar(v,sizeof(v),false,);,ds,:=0;,vs,:=true;q1:=s;/v,用于判断是否在队列，,q,表示当前的点,head:=1;tail:=1;while head,dk+ak,bk,i,then begin /,如果有更短路,dbk,i,:=,dk+ak,bk,i,;/,赋新值,if not,vbk,i,then begin /,如果不在队列，加入,inc(tail,);,qtail,:=,bk,i,;,vbk,i,:=true;/,表示已加入队列,end;end;,vk,:=false;/,表示从队列中弹出,inc(head,);end;end;,spfa,时间复杂度方面要看,RP,，在大部分情况下是,O(NM)M,一般是个位数，但如果是变态佬出的数据,M,最坏可能是边数，不过几率很低，就像在球场上踢球踩到,一样。,也是求单源最短路，不过如果要求出整个图的最短路复杂度也只是,O(N,2,M),大部分情况下还是比,floyd,快的。,比较,Floyd,Dijkstra,Spfa,时间,O(N,3,),O(N,2,),O(NM),算法打字难易度,极易,较麻烦,理解的话就不难，除非像我之前,用途,十分广泛，后两者对应的它几乎都能完成，时间问题而已,单源最短路，前提是没有负数，,OJ,有一题有负数的就不能用,单源最短路，要整幅图找也行，数据一般也不坑爹，建议使用,经典例题,Usaco,3.2butter,oj,上有一样的题目,(1370),这题我是用,spfa,做的，如果大家想测试不同方法的时间效率的话可以交到,usaco,上，他会帮你计时的。,Spfa,程序,program butter;,var,p,k,c,m,n,i,j,x,y,z,tt,head,tail,min:longint,;,f1,d,q:array1.1000of,longint,;,a,b:array0.1000,0.1000of,longint,;,v:array1.1000of,boolean,;,procedure,spfa(s:longint,);,var,i,k:longint,;,begin,fillchar(d,sizeof(d),$7f);,fillchar(v,sizeof(v),false,);,ds,:=0;,vs,:=true;q1:=s;,head:=1;tail:=1;,while head,dk+ak,bk,i,then begin,dbk,i,:=,dk+ak,bk,i,;,if not,vbk,i,then begin,inc(tail,);,qtail,:=,bk,i,;,vbk,i,:=true;,end;,end;,vk,:=false;,inc(head,);,end;,end;,begin,readln(n,p,c,);,for i:=1 to n do,begin,readln(k,);,inc(f1k);,end;,for i:=1 to c do,begin,readln(x,y,z,);,inc(bx,0);,bx,bx,0:=y;,ax,y,:=z;,inc(by,0);,by,by,0:=x;,ay,x,:=z;,end;,min:=,maxlongint,;,for i:=1 to p do,begin,tt,:=0;,spfa(i,);,for j:=1 to p do,inc(tt,dj,*f1j);,if,tt,min then min:=,tt,;,end;,writeln(min,);,end.,谢谢,BY：JCR,EM：lzoi_,