再看最短路算法 1 —— 单源最短路
再看最短路算法 1 —— 单源最短路
学了多年的算法，最短路问题相当之常见————
好久没写过最短路的问题了，直到昨天闲的无聊来了一题——BZOJ3402（HansBug:额才发现我弱到只能刷水的地步了TT）
一看这不是明显的单源最短路么呵呵。。。于是直接上来来了个dijkstra，而且用的是邻接表存储图——
Submit之后，结果却是——
我立刻被雷到了QAQ。。。于是立刻改写spfa，结果——
4000ms+（估计还不止）和192ms究竟是怎样的差距啊QAQ，本人虽然早都听说过spfa的强大性，但是未曾想过差距会如此可怕，于是HansBug‘s Labo Online——
准备：1.dijkstra单源最短路径模板
1 type
2 point=^node;
3 node=record
4 g,w:longint;
5 next:point;
6 end;
7
8 var
9 i,j,k,l,m,n:longint;
10 a:array[0..100000] of point;
11 b,c:array[0..100000] of longint;
12 p:point;
13 procedure add(x,y,z:longint);inline;
14 var p:point;
15 begin
16 new(p);p^.g:=y;p^.w:=z;
17 p^.next:=a[x];a[x]:=p;
18 end;
19 function min(x,y:longint):longint;inline;
20 begin
21 if x<y then min:=x else min:=y;
22 end;
23 procedure dijkstra(x:longint);
24 var i,j,k,l:longint;p:point;
25 begin
26 fillchar(c,sizeof(c),0);
27 fillchar(b,sizeof(b),0);
28 c[x]:=1;
29 p:=a[x];
30 while p<>nil do
31 begin
32 if (b[p^.g]=0) and (c[p^.g]=0) then b[p^.g]:=p^.w else b[p^.g]:=min(b[p^.g],p^.w);
33 p:=p^.next;
34 end;
35
36 for i:=1 to n-1 do
37 begin
38 l:=maxlongint;k:=-1;
39 for j:=1 to n do
40 if (c[j]=0) and (b[j]>0) and (b[j]<l) then
41 begin
42 l:=b[j];k:=j;
43 end;
44 if k=-1 then break;
45 c[k]:=1;p:=a[k];
46 while p<>nil do
47 begin
48 if (c[p^.g]=0) and ((b[p^.g]=0) or (b[p^.g]>(p^.w+l))) then b[p^.g]:=p^.w+l;
49 p:=p^.next;
50 end;
51 end;
52 end;
53 begin
54 readln(n,m);
55 for i:=1 to n do a[i]:=nil;
56 for i:=1 to m do
57 begin
58 readln(j,k,l);
59 add(j,k,l);
60 end;
61 dijkstra(1);
62 for i:=1 to n do
63 case c[i] of
64 1:writeln(1,' ---> ',i,' : ',b[i]);
65 0:writeln(1,' ---> ',i,' : ','Unavailable');
66 end;
67 readln;
68 end.2.spfa单源最短路径模板
1 type
2 point=^node;
3 node=record
4 g,w:longint;
5 next:point;
6 end;
7 var
8 i,j,k,l,m,n:longint;
9 a:array[0..100000] of point;
10 b,c:array[0..1000000] of longint;
11 procedure add(x,y,z:longint);inline;
12 var p:point;
13 begin
14 new(p);p^.g:=y;p^.w:=z;
15 p^.next:=a[x];a[x]:=p;
16 end;
17 procedure spfa(x:longint);inline;
18 var f,r:longint;p:point;
19 begin
20 f:=1;r:=2;
21 fillchar(c,sizeof(c),0);
22 c[x]:=1;
23 b[1]:=x;
24 while f<r do
25 begin
26 p:=a[b[f]];
27 while p<>nil do
28 begin
29 if (c[p^.g]=0) or (c[p^.g]>(p^.w+c[b[f]])) then
30 begin
31 c[p^.g]:=p^.w+c[b[f]];
32 b[r]:=p^.g;
33 inc(r);
34 end;
35 p:=p^.next;
36 end;
37 inc(f);
38 end;
39 for i:=1 to n do dec(c[i]);
40 end;
41 begin
42 readln(n,m);
43 for i:=1 to n do a[i]:=nil;
44 for i:=1 to m do
45 begin
46 readln(j,k);
47 add(j,k,1);add(k,j,1);
48 end;
49 spfa(1);
50 for i:=1 to n do
51 case c[i] of
52 -1:writeln(1,' ---> ',i,' : ','Unavailable');
53 else writeln(1,' ---> ',i,' : ',c[i]);
54 end;
55 readln;
56 end.3.bat对拍小程序
（PS：由于Bellman-Ford算法具有超高的时空浪费量，还有Floyd一般不用于单源最短路，所以只准备这些）
还有：这次采用的对拍模式如下——模拟一般OI赛制上的10组数据，30%数据满足规模为N<=10000 M<=100000;60%的数据满足规模为N<=30000 M<=200000；100%的数据满足N<=50000 M<=1000000。每10组这样的数据为一组，多组测试
公布结果——在30%的数据时，spfa用时200ms多点，dijkstra用时300ms多点
在60%数据时，spfa用时400ms多点，dijkstra用时1500-1800ms
在100%数据时，dpfa用时1300ms+，dijkstra用时11000-14000ms
差距就是——10倍，尤其是数量上去之后
原因——dijkstra里面最怕的就是一边接着一遍的扫描最小值，而且事实证明，如果像我原来预想的样子写堆优化的话——1.堆优化难写，因为不仅仅涉及到删除和加入新值 2.代码量会成倍的扩大。也就是说真正的成了O(N^2).而spfa是与边的密度相关的，且减少了许多的松弛操作
总结：事实的效果才能说明一切。更何况这个里面是随机生成的数据而不是OI的时候有意构造出来的更加强的数据。。。
（附：用于对拍的batch）
1 @echo off
2 :2
3 set /a s=0
4 cls
5 :1
6 set /a s=s+1
7 echo Test %s%
8 if %s% leq 3 (
9 echo 10000 100000|fuckpath.exe >path.in
10 goto 4)
11 if %s% leq 6 (
12 echo 30000 200000|fuckpath.exe >path.in
13 goto 4)
14 if %s% leq 10 (
15 echo 50000 1000000|fuckpath.exe >path.in
16 goto 4)
17 :4
18 echo.|time
19 type path.in|spfa.exe >spfa.out
20 echo.|time
21 echo.|time
22 type path.in|dijkstra.exe >dijkstra.out
23 echo.|time
24 fc dijkstra.out spfa.out
25 if %s%==10 (goto 3)
26 goto 1
27 :3
28 pause
29 goto 2