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

dijkstra就不解释了，随便一本算法书上都有，只贴程序（百度会把缩进干掉的，将就着看吧）spfa我以前贴过，自己看：/hefeizhousiyuan/blog/item/99114feac0c973d5d539c9d7.html理论上来讲dij时间是O(ElogV)，而spfa是O(kE)（k约为2)，但是spfa实质上只是bellman-ford的一种实现方法，依然可以构造出数据是它的时间复杂度退化成O(VE)的。不过，在绝大多数情况下，spfa的性能还是不会比dij+heap差的，最重要的是spfa代码更短。以usaco 3.2 butter来比较，spfa稍胜一些。（V=700,E=1450,调用最短路过程700次）dijkstra + heapExecuting. Test 1: TEST OK 0.000 secs, 248 KB Test 2: TEST OK 0.000 secs, 248 KB Test 3: TEST OK 0.000 secs, 252 KB Test 4: TEST OK 0.011 secs, 248 KB Test 5: TEST OK 0.011 secs, 252 KB Test 6: TEST OK 0.032 secs, 252 KB Test 7: TEST OK 0.162 secs, 252 KB Test 8: TEST OK 0.313 secs, 280 KB Test 9: TEST OK 0.626 secs, 280 KB Test 10: TEST OK 0.594 secs, 284 KBspfaExecuting. Test 1: TEST OK 0.000 secs, 244 KB Test 2: TEST OK 0.000 secs, 240 KB Test 3: TEST OK 0.000 secs, 240 KB Test 4: TEST OK 0.000 secs, 240 KB Test 5: TEST OK 0.011 secs, 244 KB Test 6: TEST OK 0.022 secs, 244 KB Test 7: TEST OK 0.065 secs, 244 KB Test 8: TEST OK 0.130 secs, 272 KB Test 9: TEST OK 0.259 secs, 276 KB Test 10: TEST OK 0.248 secs, 276 KBdijkstra+heap（邻接表实现）Type link = node; node = record v , w : integer; next : link; end;Const maxn = 1000;Var n , m , l : integer; a : array1.maxn of link; hp : array1.maxn of integer; t : array0.maxn of record v : integer; d : longint; end;Procedure insert(x , y , w : integer);var p : link;begin new(p); p.v := y;p.w := w; p.next := ax;ax := p;end;Procedure init;var i , x , y , w : integer;begin readln(n , m); for i := 1 to m do begin readln(x , y , w); insert(x , y , w); end;end;procedure swap(a , b : integer);begin t0 := ta; ta := tb; tb := t0; hpta.v := a; hptb.v := b;end;procedure setheap(st : integer);var i : integer;begin for i := 1 to n do begin ti.v := i; ti.d := maxlongint; hpi := i; end; tst.d := 0; swap(1 , st);end;procedure down(x : integer);var i , j , m : integer;begin i := x; while i * 2 = l do (* *) begin j := i * 2; if (i * 2 + 1 = l) and (ti * 2 + 1.d tj.d then begin swap(i , j); i := j; end else break; end;end;procedure up(x : integer);var i : integer;begin i := x; while i 1 do begin if ti.d ti div 2.d then begin swap(i , i div 2); i := i div 2; end else break; end;end;procedure relax(u , v : integer; w : longint);begin if t hpu .d + w 0 do begin u := t1.v; swap(1 , l); dec(l); down(1); p := au; while p nil do begin if hpp.v = l then relax(u , p.v , p.w); p := p.next; end; end;end;Procedure print;var i :