再看最短路算法 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一枝花算不算浪漫

[jQuery学习系列六]6-jQuery实际操作小案例

467170
来自专栏数据结构与算法

BZOJ4668: 冷战(并查集)

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

8520
来自专栏安智客

密码发展史之古典密码

密码(Cryptology)是一种用来混淆的技术,它希望将正常的、可识别的信息转变为无法识别的信息。密码学是一个即古老又新兴的学科,密码学一词源自希腊文“kry...

29370
来自专栏牛客网

网易考拉前端开奖啦~分享一波面筋

内推投了十几二十家公司,大多没消息。BAT都没有面(百度投了没消息,腾讯打了一次电话来没接到就变灰了,阿里问我有没兴趣改测试岗(表示没兴趣))。于是最终面试的就...

13420
来自专栏飞总聊IT

大数据那些事(10):李逵麻子,李鬼坑人--BigTable的数据模型

今天我们回归技术路线,讲讲Google三驾马车里的BigTable。以前有个说法叫做麻子不叫麻子,叫坑人。取其原意是满脸是坑的人,谐音表示人被坑了。我们知道水浒...

41870
来自专栏大数据挖掘DT机器学习

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

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

53550
来自专栏落影的专栏

OpenGL ES实践教程(九)OpenGL与视频混合

前言 前面的实践教程: OpenGL ES实践教程1-Demo01-AVPlayer OpenGL ES实践教程2-Demo02-摄像头采集数据和渲染 O...

59550
来自专栏大数据文摘

UK DN AS NN WG UX AA:这是一条加密推送!

14740
来自专栏大大的微笑

观察者模式详解

观察者模式是众多软件设计模式中的一种,又称发布订阅模式.被观察的对象发生了变化,观察者对象们可以第一时间收到通知, 并作出相应的处理,例如作为一家餐馆的会员...

236100
来自专栏飞总聊IT

大数据那些事(10):李逵麻子,李鬼坑人--BigTable的数据模型

今天我们回归技术路线,讲讲Google三驾马车里的BigTable。以前有个说法叫做麻子不叫麻子,叫坑人。取其原意是满脸是坑的人,谐音表示人被坑了。我们知道水浒...

317100

扫码关注云+社区

领取腾讯云代金券