[算法][最短路]dijkstra + heap 和 spfa 程序,时间比较

《[算法][最短路]dijkstra + heap 和 spfa 程序,时间比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、dijkstra就不解释了，随便一本算法书上都有，只贴程序（百度会把缩进干掉的，将就着看吧）spfa我以前贴过，自己看：http://hi.baidu.com/hefeizhousiyuan/blog/item/99114feac0c973d5d539c9d7.html理论上来讲dij时间是O(ElogV)，而spfa是O(kE)（k约为2)，但是spfa实质上只是bellman-ford的一种实现方法，依然可以构造出数据是它的时间复杂度退化成O(VE)的。不过，在绝大多数情况下，spfa的性能还是不会比dij+heap差的，最重要的是spfa代码更

2、短。以usaco3.2butter来比较，spfa稍胜一些。（V=700,E=1450,调用最短路过程700次）dijkstra+heapExecuting...  Test1:TESTOK[0.000secs,248KB]  Test2:TESTOK[0.000secs,248KB]  Test3:TESTOK[0.000secs,252KB]  Test4:TESTOK[0.011secs,248KB]  Test5:TESTOK[0.011secs,252KB]  Test6:TESTOK[0.032secs,252KB]  Test7:TES

3、TOK[0.162secs,252KB]  Test8:TESTOK[0.313secs,280KB]  Test9:TESTOK[0.626secs,280KB]  Test10:TESTOK[0.594secs,284KB]spfaExecuting...  Test1:TESTOK[0.000secs,244KB]  Test2:TESTOK[0.000secs,240KB]  Test3:TESTOK[0.000secs,240KB]  Test4:TESTOK[0.000secs,240KB]  Test5:TESTOK[0.011secs

4、,244KB]  Test6:TESTOK[0.022secs,244KB]  Test7:TESTOK[0.065secs,244KB]  Test8:TESTOK[0.130secs,272KB]  Test9:TESTOK[0.259secs,276KB]  Test10:TESTOK[0.248secs,276KB]dijkstra+heap（邻接表实现）Typelink=^node;    node=record             v,w:integer;             next:link;           end;Co

5、nst      maxn=1000;Var    n,m,l:integer;    a  :array[1..maxn]oflink;    hp:array[1..maxn]ofinteger;    t  :array[0..maxn]ofrecord                              v:integer;                              d:longint;                            end;Procedureinsert(x,y,w:integer);varp:

6、link;begin   new(p);   p^.v:=y;p^.w:=w;   p^.next:=a[x];a[x]:=p;end;Procedureinit;var     i,x,y,w:integer;begin   readln(n,m);   fori:=1tomdo   begin     readln(x,y,w);     insert(x,y,w);   end;end;procedureswap(a,b:integer);begin   t[0]:=t[a];   t[a]:=t[b];   t[b]:=t[0];   hp[

7、t[a].v]:=a;   hp[t[b].v]:=b;end;proceduresetheap(st:integer);vari  :integer;begin   fori:=1tondo   begin     t[i].v:=i;     t[i].d:=maxlongint;     hp[i]:=i;   end;   t[st].d:=0;   swap(1,st);end;proceduredown(x:integer);vari,j,m:integer;begin   i:=x;   whilei*2<=ldo   (**)   b

8、egin     j:=i*2;     if(i*2+1<=l)and(t[i*2+1].d