# 再看最短路算法 1 —— 单源最短路

Submit之后，结果却是——

4000ms+（估计还不止）和192ms究竟是怎样的差距啊QAQ，本人虽然早都听说过spfa的强大性，但是未曾想过差距会如此可怕，于是HansBug‘s Labo Online——

``` 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;
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
55      for i:=1 to n do a[i]:=nil;
56      for i:=1 to m do
57          begin
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;
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;
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
43         for i:=1 to n do a[i]:=nil;
44         for i:=1 to m do
45                 begin
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;
56 end.```

3.bat对拍小程序

（PS：由于Bellman-Ford算法具有超高的时空浪费量，还有Floyd一般不用于单源最短路，所以只准备这些）

（附：用于对拍的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```

251 篇文章37 人订阅

0 条评论

## 相关文章

467170

### BZOJ4668: 冷战(并查集)

• 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第

8520

29370

13420

41870

### Python NLTK自然语言处理：词干、词形与MaxMatch算法

CSDN:白马负金羁 自然语言处理是计算机科学领域与人工智能领域中的一个重要方向。自然语言工具箱（NLTK，Natural Language Toolkit）...

53550

59550

14740

236100

317100