最短路各种算法稠密图稀疏图时间分析

feiliboos

浏览: 665187 次

最近访客更多访客>>

songhait

jacket233

hjc5345

Java_FiRe

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1141)

社区版块

存档分类

2012-03 ( 21)
2012-02 ( 54)
2012-01 ( 68)
更多存档...

分别有下面这几种算法（heap写了好久 T T 。。）

其中未注明LIST的SPFA 和 dij 是邻接矩阵的形式。

heap是手写的堆，邻接表存图。priority指的是调用C++里的STL。

Dijkstra Dijkstra_priority Dijkstra_List Dijkstra_List_priority Dijkstra_heap SPFA SPFA_List Floyd Bellman
稠密图我建图是任意两点均有路径，对角线都是0。。求得的最短路所有起点都是1，终点都是n（矩阵的大小）
下面是稠密图的时间统计，因为矩阵不能开太大，所以最大开了1250*1250。除了n = 10 都是秒过就统计一次，其他均生成三次数据。
时间单位是ms。
稠密图总结：（可以是用邻接矩阵的情况）
1、如果n不大，可以用邻接矩阵的话，dijkstra是最好的选择，写起来比较快而且速度也很快。其次是SPFA，写起来比较好写。
2、floyd 这个算法，n大于300就最好不要用了，很有可能跑1秒以上了。
3、bellman-ford ，n大于200就不要用了，比floyd还耗时间 = =。。。

稀疏图的m 是边数，n是点数。
稀疏图总结：（前面的n比较小时可以用邻接矩阵，后面的floyd 啊 dijkstra等不能使用邻接矩阵的就删掉不考虑了）
1、稀疏图，明显感觉用邻接表的算法占优势了。
2、bellman 超过50000边就不要用了。
3、heap的表现可以说是最好的。
4、超过3000个点就不要用dijkstra 加邻接表不加任何优化的那种。
5、超过500000条边就不要用SPFA加邻接表了。
6、综上，dijkstra + priority 邻接表是最好的选择。虽然比heap慢一点，跑3W点 300W边和heap没差多少。
7、priority坏处就是，不能在队列里修改值，如果进队多次，可能空间满了。。
8、特别恶心的可以用heap ，一般的恶心用priority足以^ ^

附稠密图和稀疏图的时间统计
稠密图

n = 10;************************************* Dijkstra time is 0 Dijkstra_priority time is 0 Dijkstra_List time is 0 Dijkstra_List_priority time is 0 Dijkstra_heap time is 0 SPFA time is 0 SPFA_List time is 0 Floyd time is 0 Bellman time is 0 The answer of SPFA is 5782 The answer of SPFA_List is 5782 The answer of Dijkstra is 5782 The answer of Dijkstra_priority is 5782 The answer of Dijkstra_List is 5782 The answer of Dijkstra_List_priority is 5782 The answer of Floyd is 5782 The answer of BellmanFord is 5782 The answer of Dijkstra_Heap is 5782 _________________________________________________ n == 100;******************************** Dijkstra time is 0 Dijkstra_priority time is 0 Dijkstra_List time is 1 Dijkstra_List_priority time is 0 Dijkstra_heap time is 1 SPFA time is 0 SPFA_List time is 1 Floyd time is 14 Bellman time is 27 The answer of SPFA is 2400 The answer of SPFA_List is 2400 The answer of Dijkstra is 2400 The answer of Dijkstra_priority is 2400 The answer of Dijkstra_List is 2400 The answer of Dijkstra_List_priority is 2400 The answer of Floyd is 2400 The answer of BellmanFord is 2400 The answer of Dijkstra_Heap is 2400 _________________________________________________ Dijkstra time is 0 Dijkstra_priority time is 0 Dijkstra_List time is 0 Dijkstra_List_priority time is 1 Dijkstra_heap time is 0 SPFA time is 1 SPFA_List time is 0 Floyd time is 16 Bellman time is 27 The answer of SPFA is 365 The answer of SPFA_List is 365 The answer of Dijkstra is 365 The answer of Dijkstra_priority is 365 The answer of Dijkstra_List is 365 The answer of Dijkstra_List_priority is 365 The answer of Floyd is 365 The answer of BellmanFord is 365 The answer of Dijkstra_Heap is 365 _________________________________________________ Dijkstra time is 1 Dijkstra_priority time is 0 Dijkstra_List time is 1 Dijkstra_List_priority time is 1 Dijkstra_heap time is 0 SPFA time is 0 SPFA_List time is 1 Floyd time is 15 Bellman time is 29 The answer of SPFA is 1411 The answer of SPFA_List is 1411 The answer of Dijkstra is 1411 The answer of Dijkstra_priority is 1411 The answer of Dijkstra_List is 1411 The answer of Dijkstra_List_priority is 1411 The answer of Floyd is 1411 The answer of BellmanFord is 1411 The answer of Dijkstra_Heap is 1411 _________________________________________________ n = 150;************************************* Dijkstra time is 1 Dijkstra_priority time is 1 Dijkstra_List time is 1 Dijkstra_List_priority time is 1 Dijkstra_heap time is 1 SPFA time is 0 SPFA_List time is 1 Floyd time is 49 Bellman time is 105 The answer of SPFA is 1797 The answer of SPFA_List is 1797 The answer of Dijkstra is 1797 The answer of Dijkstra_priority is 1797 The answer of Dijkstra_List is 1797 The answer of Dijkstra_List_priority is 1797 The answer of Floyd is 1797 The answer of BellmanFord is 1797 The answer of Dijkstra_Heap is 1797 _________________________________________________ Dijkstra time is 1 Dijkstra_priority time is 1 Dijkstra_List time is 1 Dijkstra_List_priority time is 1 Dijkstra_heap time is 0 SPFA time is 1 SPFA_List time is 1 Floyd time is 51 Bellman time is 113 The answer of SPFA is 1358 The answer of SPFA_List is 1358 The answer of Dijkstra is 1358 The answer of Dijkstra_priority is 1358 The answer of Dijkstra_List is 1358 The answer of Dijkstra_List_priority is 1358 The answer of Floyd is 1358 The answer of BellmanFord is 1358 The answer of Dijkstra_Heap is 1358 _________________________________________________ Dijkstra time is 0 Dijkstra_priority time is 1 Dijkstra_List time is 1 Dijkstra_List_priority time is 1 Dijkstra_heap time is 1 SPFA time is 1 SPFA_List time is 0 Floyd time is 50 Bellman time is 203 The answer of SPFA is 1633 The answer of SPFA_List is 1633 The answer of Dijkstra is 1633 The answer of Dijkstra_priority is 1633 The answer of Dijkstra_List is 1633 The answer of Dijkstra_List_priority is 1633 The answer of Floyd is 1633 The answer of BellmanFord is 1633 The answer of Dijkstra_Heap is 1633 _________________________________________________ n = 200;****************************************** Dijkstra time is 1 Dijkstra_priority time is 2 Dijkstra_List time is 1 Dijkstra_List_priority time is 2 Dijkstra_heap time is 1 SPFA time is 1 SPFA_List time is 1 Floyd time is 234 Bellman time is 279 The answer of SPFA is 382 The answer of SPFA_List is 382 The answer of Dijkstra is 382 The answer of Dijkstra_priority is 382 The answer of Dijkstra_List is 382 The answer of Dijkstra_List_priority is 382 The answer of Floyd is 382 The answer of BellmanFord is 382 The answer of Dijkstra_Heap is 382 _________________________________________________ Dijkstra time is 1 Dijkstra_priority time is 2 Dijkstra_List time is 1 Dijkstra_List_priority time is 2 Dijkstra_heap time is 0 SPFA time is 1 SPFA_List time is 1 Floyd time is 119 Bellman time is 256 The answer of SPFA is 970 The answer of SPFA_List is 970 The answer of Dijkstra is 970 The answer of Dijkstra_priority is 970 The answer of Dijkstra_List is 970 The answer of Dijkstra_List_priority is 970 The answer of Floyd is 970 The answer of BellmanFord is 970 The answer of Dijkstra_Heap is 970 _________________________________________________ Dijkstra time is 0 Dijkstra_priority time is 1 Dijkstra_List time is 0 Dijkstra_List_priority time is 3 Dijkstra_heap time is 0 SPFA time is 1 SPFA_List time is 1 Floyd time is 122 Bellman time is 250 The answer of SPFA is 407 The answer of SPFA_List is 407 The answer of Dijkstra is 407 The answer of Dijkstra_priority is 407 The answer of Dijkstra_List is 407 The answer of Dijkstra_List_priority is 407 The answer of Floyd is 407 The answer of BellmanFord is 407 The answer of Dijkstra_Heap is 407 _________________________________________________ n = 300;****************************************** Dijkstra time is 1 Dijkstra_priority time is 2 Dijkstra_List time is 2 Dijkstra_List_priority time is 4 Dijkstra_heap time is 2 SPFA time is 3 SPFA_List time is 3 Floyd time is 394 Bellman time is 1066 The answer of SPFA is 543 The answer of SPFA_List is 543 The answer of Dijkstra is 543 The answer of Dijkstra_priority is 543 The answer of Dijkstra_List is 543 The answer of Dijkstra_List_priority is 543 The answer of Floyd is 543 The answer of BellmanFord is 543 The answer of Dijkstra_Heap is 543 _________________________________________________ Dijkstra time is 2 Dijkstra_priority time is 4 Dijkstra_List time is 2 Dijkstra_List_priority time is 4 Dijkstra_heap time is 1 SPFA time is 2 SPFA_List time is 3 Floyd time is 542 Bellman time is 1081 The answer of SPFA is 628 The answer of SPFA_List is 628 The answer of Dijkstra is 628 The answer of Dijkstra_priority is 628 The answer of Dijkstra_List is 628 The answer of Dijkstra_List_priority is 628 The answer of Floyd is 628 The answer of BellmanFord is 628 The answer of Dijkstra_Heap is 628 _________________________________________________ Dijkstra time is 2 Dijkstra_priority time is 3 Dijkstra_List time is 3 Dijkstra_List_priority time is 4 Dijkstra_heap time is 2 SPFA time is 2 SPFA_List time is 3 Floyd time is 439 Bellman time is 1009 The answer of SPFA is 1000 The answer of SPFA_List is 1000 The answer of Dijkstra is 1000 The answer of Dijkstra_priority is 1000 The answer of Dijkstra_List is 1000 The answer of Dijkstra_List_priority is 1000 The answer of Floyd is 1000 The answer of BellmanFord is 1000 The answer of Dijkstra_Heap is 1000 _________________________________________________ n = 500;****************************************** Dijkstra time is 5 Dijkstra_priority time is 7 Dijkstra_List time is 6 Dijkstra_List_priority time is 11 Dijkstra_heap time is 4 SPFA time is 9 SPFA_List time is 10 Floyd time is 3098 Bellman time is 5135 The answer of SPFA is 618 The answer of SPFA_List is 618 The answer of Dijkstra is 618 The answer of Dijkstra_priority is 618 The answer of Dijkstra_List is 618 The answer of Dijkstra_List_priority is 618 The answer of Floyd is 618 The answer of BellmanFord is 618 The answer of Dijkstra_Heap is 618 _________________________________________________ Dijkstra time is 7 Dijkstra_priority time is 8 Dijkstra_List time is 7 Dijkstra_List_priority time is 12 Dijkstra_heap time is 5 SPFA time is 10 SPFA_List time is 12 Floyd time is 2625 Bellman time is 5268 The answer of SPFA is 496 The answer of SPFA_List is 496 The answer of Dijkstra is 496 The answer of Dijkstra_priority is 496 The answer of Dijkstra_List is 496 The answer of Dijkstra_List_priority is 496 The answer of Floyd is 496 The answer of BellmanFord is 496 The answer of Dijkstra_Heap is 496 _________________________________________________ Dijkstra time is 5 Dijkstra_priority time is 6 Dijkstra_List time is 8 Dijkstra_List_priority time is 12 Dijkstra_heap time is 5 SPFA time is 9 SPFA_List time is 13 Floyd time is 2784 Bellman time is 5328 The answer of SPFA is 348 The answer of SPFA_List is 348 The answer of Dijkstra is 348 The answer of Dijkstra_priority is 348 The answer of Dijkstra_List is 348 The answer of Dijkstra_List_priority is 348 The answer of Floyd is 348 The answer of BellmanFord is 348 The answer of Dijkstra_Heap is 348 _________________________________________________ n = 750;****************************************** Dijkstra time is 11 Dijkstra_priority time is 12 Dijkstra_List time is 80 Dijkstra_List_priority time is 19 Dijkstra_heap time is 8 SPFA time is 18 SPFA_List time is 23 Floyd time is 8399 Bellman time is 15542 The answer of SPFA is 320 The answer of SPFA_List is 320 The answer of Dijkstra is 320 The answer of Dijkstra_priority is 320 The answer of Dijkstra_List is 320 The answer of Dijkstra_List_priority is 320 The answer of Floyd is 320 The answer of BellmanFord is 320 The answer of Dijkstra_Heap is 320 _________________________________________________ Dijkstra time is 13 Dijkstra_priority time is 14 Dijkstra_List time is 89 Dijkstra_List_priority time is 22 Dijkstra_heap time is 12 SPFA time is 22 SPFA_List time is 32 Floyd time is 8316 Bellman time is 14367 The answer of SPFA is 252 The answer of SPFA_List is 252 The answer of Dijkstra is 252 The answer of Dijkstra_priority is 252 The answer of Dijkstra_List is 252 The answer of Dijkstra_List_priority is 252 The answer of Floyd is 252 The answer of BellmanFord is 252 The answer of Dijkstra_Heap is 252 _________________________________________________ Dijkstra time is 13 Dijkstra_priority time is 13 Dijkstra_List time is 13 Dijkstra_List_priority time is 20 Dijkstra_heap time is 10 SPFA time is 21 SPFA_List time is 22 Floyd time is 8072 Bellman time is 14145 The answer of SPFA is 443 The answer of SPFA_List is 443 The answer of Dijkstra is 443 The answer of Dijkstra_priority is 443 The answer of Dijkstra_List is 443 The answer of Dijkstra_List_priority is 443 The answer of Floyd is 443 The answer of BellmanFord is 443 The answer of Dijkstra_Heap is 443 _________________________________________________ n = 1000;****************************************** Dijkstra time is 24 Dijkstra_priority time is 21 Dijkstra_List time is 26 Dijkstra_List_priority time is 38 Dijkstra_heap time is 16 SPFA time is 32 SPFA_List time is 53 Floyd time is 14839 Bellman time is 30615 The answer of SPFA is 230 The answer of SPFA_List is 230 The answer of Dijkstra is 230 The answer of Dijkstra_priority is 230 The answer of Dijkstra_List is 230 The answer of Dijkstra_List_priority is 230 The answer of Floyd is 230 The answer of BellmanFord is 230 The answer of Dijkstra_Heap is 230 _________________________________________________ Dijkstra time is 22 Dijkstra_priority time is 25 Dijkstra_List time is 27 Dijkstra_List_priority time is 46 Dijkstra_heap time is 15 SPFA time is 41 SPFA_List time is 56 Floyd time is 14106 Bellman time is 28779 The answer of SPFA is 275 The answer of SPFA_List is 275 The answer of Dijkstra is 275 The answer of Dijkstra_priority is 275 The answer of Dijkstra_List is 275 The answer of Dijkstra_List_priority is 275 The answer of Floyd is 275 The answer of BellmanFord is 275 The answer of Dijkstra_Heap is 275 _________________________________________________ Dijkstra time is 29 Dijkstra_priority time is 22 Dijkstra_List time is 24 Dijkstra_List_priority time is 35 Dijkstra_heap time is 22 SPFA time is 31 SPFA_List time is 61 Floyd time is 13779 Bellman time is 28682 The answer of SPFA is 280 The answer of SPFA_List is 280 The answer of Dijkstra is 280 The answer of Dijkstra_priority is 280 The answer of Dijkstra_List is 280 The answer of Dijkstra_List_priority is 280 The answer of Floyd is 280 The answer of BellmanFord is 280 The answer of Dijkstra_Heap is 280 _________________________________________________ n = 1250******************************************* Dijkstra time is 97 Dijkstra_priority time is 31 Dijkstra_List time is 39 Dijkstra_List_priority time is 48 Dijkstra_heap time is 24 SPFA time is 54 SPFA_List time is 72 Floyd time is 25924 Bellman time is 55248 The answer of SPFA is 185 The answer of SPFA_List is 185 The answer of Dijkstra is 185 The answer of Dijkstra_priority is 185 The answer of Dijkstra_List is 185 The answer of Dijkstra_List_priority is 185 The answer of Floyd is 185 The answer of BellmanFord is 185 The answer of Dijkstra_Heap is 185 _________________________________________________ Dijkstra time is 35 Dijkstra_priority time is 34 Dijkstra_List time is 62 Dijkstra_List_priority time is 59 Dijkstra_heap time is 24 SPFA time is 63 SPFA_List time is 77 Floyd time is 25744 Bellman time is 56472 The answer of SPFA is 129 The answer of SPFA_List is 129 The answer of Dijkstra is 129 The answer of Dijkstra_priority is 129 The answer of Dijkstra_List is 129 The answer of Dijkstra_List_priority is 129 The answer of Floyd is 129 The answer of BellmanFord is 129 The answer of Dijkstra_Heap is 129 _________________________________________________ Dijkstra time is 47 Dijkstra_priority time is 30 Dijkstra_List time is 42 Dijkstra_List_priority time is 68 Dijkstra_heap time is 43 SPFA time is 72 SPFA_List time is 86 Floyd time is 25993 Bellman time is 56552 The answer of SPFA is 188 The answer of SPFA_List is 188 The answer of Dijkstra is 188 The answer of Dijkstra_priority is 188 The answer of Dijkstra_List is 188 The answer of Dijkstra_List_priority is 188 The answer of Floyd is 188 The answer of BellmanFord is 188 The answer of Dijkstra_Heap is 188
稀疏图

n = 500; m = 1000;************************************* Dijkstra time is 3 Dijkstra_priority time is 0 Dijkstra_List time is 3 Dijkstra_List_priority time is 2 Dijkstra_heap time is 0 SPFA time is 0 SPFA_List time is 0 Bellman time is 18 The answer of SPFA is 139408 The answer of SPFA_List is 139408 The answer of Dijkstra is 139408 The answer of Dijkstra_priority is 139408 The answer of Dijkstra_List is 139408 The answer of Dijkstra_List_priority is 139408 The answer of BellmanFord is 139408 The answer of Dijkstra_Heap is 139408 _________________________________________________ n = 500; m = 5000; Dijkstra time is 5 Dijkstra_priority time is 2 Dijkstra_List time is 3 Dijkstra_List_priority time is 2 Dijkstra_heap time is 0 SPFA time is 3 SPFA_List time is 2 Bellman time is 85 The answer of SPFA is 18603 The answer of SPFA_List is 18603 The answer of Dijkstra is 18603 The answer of Dijkstra_priority is 18603 The answer of Dijkstra_List is 18603 The answer of Dijkstra_List_priority is 18603 The answer of BellmanFord is 18603 The answer of Dijkstra_Heap is 18603 _________________________________________________ n = 500; m = 10000; Dijkstra time is 2 Dijkstra_priority time is 5 Dijkstra_List time is 3 Dijkstra_List_priority time is 2 Dijkstra_heap time is 0 SPFA time is 3 SPFA_List time is 2 Bellman time is 153 The answer of SPFA is 7388 The answer of SPFA_List is 7388 The answer of Dijkstra is 7388 The answer of Dijkstra_priority is 7388 The answer of Dijkstra_List is 7388 The answer of Dijkstra_List_priority is 7388 The answer of BellmanFord is 7388 The answer of Dijkstra_Heap is 7388 _________________________________________________ Dijkstra time is 5 Dijkstra_priority time is 5 Dijkstra_List time is 3 Dijkstra_List_priority time is 2 Dijkstra_heap time is 0 SPFA time is 3 SPFA_List time is 2 Bellman time is 180 The answer of SPFA is 13578 The answer of SPFA_List is 13578 The answer of Dijkstra is 13578 The answer of Dijkstra_priority is 13578 The answer of Dijkstra_List is 13578 The answer of Dijkstra_List_priority is 13578 The answer of BellmanFord is 13578 The answer of Dijkstra_Heap is 13578 _________________________________________________ n = 500; m = 50000; Dijkstra time is 7 Dijkstra_priority time is 5 Dijkstra_List time is 3 Dijkstra_List_priority time is 5 Dijkstra_heap time is 2 SPFA time is 8 SPFA_List time is 5 Bellman time is 1023 The answer of SPFA is 2771 The answer of SPFA_List is 2771 The answer of Dijkstra is 2771 The answer of Dijkstra_priority is 2771 The answer of Dijkstra_List is 2771 The answer of Dijkstra_List_priority is 2771 The answer of BellmanFord is 2771 The answer of Dijkstra_Heap is 2771 _________________________________________________ Dijkstra time is 5 Dijkstra_priority time is 5 Dijkstra_List time is 5 Dijkstra_List_priority time is 5 Dijkstra_heap time is 0 SPFA time is 7 SPFA_List time is 5 Bellman time is 828 The answer of SPFA is 2642 The answer of SPFA_List is 2642 The answer of Dijkstra is 2642 The answer of Dijkstra_priority is 2642 The answer of Dijkstra_List is 2642 The answer of Dijkstra_List_priority is 2642 The answer of BellmanFord is 2642 The answer of Dijkstra_Heap is 2642 _________________________________________________ n = 500; m = 100000; Dijkstra time is 5 Dijkstra_priority time is 5 Dijkstra_List time is 25 Dijkstra_List_priority time is 15 Dijkstra_heap time is 5 SPFA time is 10 SPFA_List time is 15 Bellman time is 1678 The answer of SPFA is 1126 The answer of SPFA_List is 1126 The answer of Dijkstra is 1126 The answer of Dijkstra_priority is 1126 The answer of Dijkstra_List is 1126 The answer of Dijkstra_List_priority is 1126 The answer of BellmanFord is 1126 The answer of Dijkstra_Heap is 1126 _________________________________________________ Dijkstra time is 5 Dijkstra_priority time is 8 Dijkstra_List time is 5 Dijkstra_List_priority time is 10 Dijkstra_heap time is 10 SPFA time is 10 SPFA_List time is 27 Bellman time is 1543 The answer of SPFA is 717 The answer of SPFA_List is 717 The answer of Dijkstra is 717 The answer of Dijkstra_priority is 717 The answer of Dijkstra_List is 717 The answer of Dijkstra_List_priority is 717 The answer of BellmanFord is 717 The answer of Dijkstra_Heap is 717 n = 500; m = 200000; Dijkstra time is 7 Dijkstra_priority time is 8 Dijkstra_List time is 137 Dijkstra_List_priority time is 30 Dijkstra_heap time is 27 SPFA time is 13 SPFA_List time is 112 Bellman time is 2740 The answer of SPFA is 897 The answer of SPFA_List is 897 The answer of Dijkstra is 897 The answer of Dijkstra_priority is 897 The answer of Dijkstra_List is 897 The answer of Dijkstra_List_priority is 897 The answer of BellmanFord is 897 The answer of Dijkstra_Heap is 897 _________________________________________________ Dijkstra time is 8 Dijkstra_priority time is 7 Dijkstra_List time is 23 Dijkstra_List_priority time is 22 Dijkstra_heap time is 18 SPFA time is 12 SPFA_List time is 57 Bellman time is 3288 The answer of SPFA is 552 The answer of SPFA_List is 552 The answer of Dijkstra is 552 The answer of Dijkstra_priority is 552 The answer of Dijkstra_List is 552 The answer of Dijkstra_List_priority is 552 The answer of BellmanFord is 552 The answer of Dijkstra_Heap is 552 _________________________________________________ n = 1000; m = 10000; Dijkstra time is 18 Dijkstra_priority time is 10 Dijkstra_List time is 15 Dijkstra_List_priority time is 5 Dijkstra_heap time is 2 SPFA time is 20 SPFA_List time is 0 Bellman time is 310 The answer of SPFA is 22265 The answer of SPFA_List is 22265 The answer of Dijkstra is 22265 The answer of Dijkstra_priority is 22265 The answer of Dijkstra_List is 22265 The answer of Dijkstra_List_priority is 22265 The answer of BellmanFord is 22265 The answer of Dijkstra_Heap is 22265 _________________________________________________ Dijkstra time is 17 Dijkstra_priority time is 20 Dijkstra_List time is 10 Dijkstra_List_priority time is 3 Dijkstra_heap time is 2 SPFA time is 10 SPFA_List time is 0 Bellman time is 400 The answer of SPFA is 25732 The answer of SPFA_List is 25732 The answer of Dijkstra is 25732 The answer of Dijkstra_priority is 25732 The answer of Dijkstra_List is 25732 The answer of Dijkstra_List_priority is 25732 The answer of BellmanFord is 25732 The answer of Dijkstra_Heap is 25732 _________________________________________________ n = 1000; m = 100000; Dijkstra time is 18 Dijkstra_priority time is 12 Dijkstra_List time is 18 Dijkstra_List_priority time is 12 Dijkstra_heap time is 8 SPFA time is 25 SPFA_List time is 18 Bellman time is 3302 The answer of SPFA is 2350 The answer of SPFA_List is 2350 The answer of Dijkstra is 2350 The answer of Dijkstra_priority is 2350 The answer of Dijkstra_List is 2350 The answer of Dijkstra_List_priority is 2350 The answer of BellmanFord is 2350 The answer of Dijkstra_Heap is 2350 _________________________________________________ Dijkstra time is 17 Dijkstra_priority time is 13 Dijkstra_List time is 17 Dijkstra_List_priority time is 15 Dijkstra_heap time is 5 SPFA time is 25 SPFA_List time is 50 Bellman time is 3213 The answer of SPFA is 2706 The answer of SPFA_List is 2706 The answer of Dijkstra is 2706 The answer of Dijkstra_priority is 2706 The answer of Dijkstra_List is 2706 The answer of Dijkstra_List_priority is 2706 The answer of BellmanFord is 2706 The answer of Dijkstra_Heap is 2706 _________________________________________________ n = 1000; m = 500000; Dijkstra time is 32 Dijkstra_priority time is 20 Dijkstra_List time is 120 Dijkstra_List_priority time is 155 Dijkstra_heap time is 65 SPFA time is 60 SPFA_List time is 387 Bellman time is 12755 The answer of SPFA is 545 The answer of SPFA_List is 545 The answer of Dijkstra is 545 The answer of Dijkstra_priority is 545 The answer of Dijkstra_List is 545 The answer of Dijkstra_List_priority is 545 The answer of BellmanFord is 545 The answer of Dijkstra_Heap is 545 _________________________________________________ Dijkstra time is 32 Dijkstra_priority time is 35 Dijkstra_List time is 100 Dijkstra_List_priority time is 340 Dijkstra_heap time is 185 SPFA time is 95 SPFA_List time is 265 Bellman time is 12843 The answer of SPFA is 665 The answer of SPFA_List is 665 The answer of Dijkstra is 665 The answer of Dijkstra_priority is 665 The answer of Dijkstra_List is 665 The answer of Dijkstra_List_priority is 665 The answer of BellmanFord is 665 The answer of Dijkstra_Heap is 665 _________________________________________________ n = 3000; m = 10000 Dijkstra_List time is 100 Dijkstra_List_priority time is 5 Dijkstra_heap time is 3 SPFA_List time is 2 The answer of SPFA_List is 124335 The answer of Dijkstra_List is 124335 The answer of Dijkstra_List_priority is 124335 The answer of Dijkstra_Heap is 124335 _________________________________________________ n = 3000; m = 100000; Dijkstra_List time is 110 Dijkstra_List_priority time is 27 Dijkstra_heap time is 8 SPFA_List time is 20 The answer of SPFA_List is 9309 The answer of Dijkstra_List is 9309 The answer of Dijkstra_List_priority is 9309 The answer of Dijkstra_Heap is 9309 _________________________________________________ n = 3000; m = 500000; Dijkstra_List time is 205 Dijkstra_List_priority time is 140 Dijkstra_heap time is 125 SPFA_List time is 468 The answer of SPFA_List is 1880 The answer of Dijkstra_List is 1880 The answer of Dijkstra_List_priority is 1880 The answer of Dijkstra_Heap is 1880 _________________________________________________ n = 3000; m = 1000000; Dijkstra_List time is 373 Dijkstra_List_priority time is 340 Dijkstra_heap time is 265 SPFA_List time is 780 The answer of SPFA_List is 902 The answer of Dijkstra_List is 902 The answer of Dijkstra_List_priority is 902 The answer of Dijkstra_Heap is 902 _________________________________________________ n = 10000; m = 100000; Dijkstra_List time is 1445 Dijkstra_List_priority time is 43 Dijkstra_heap time is 22 SPFA_List time is 50 The answer of SPFA_List is 22591 The answer of Dijkstra_List is 22591 The answer of Dijkstra_List_priority is 22591 The answer of Dijkstra_Heap is 22591 _________________________________________________ n = 10000; m = 500000; Dijkstra_List time is 1453 Dijkstra_List_priority time is 192 Dijkstra_heap time is 200 SPFA_List time is 220 The answer of SPFA_List is 5972 The answer of Dijkstra_List is 5972 The answer of Dijkstra_List_priority is 5972 The answer of Dijkstra_Heap is 5972 _________________________________________________ n = 10000; m = 1000000; Dijkstra_List time is 1430 Dijkstra_List_priority time is 320 Dijkstra_heap time is 308 SPFA_List time is 645 The answer of SPFA_List is 3686 The answer of Dijkstra_List is 3686 The answer of Dijkstra_List_priority is 3686 The answer of Dijkstra_Heap is 3686 _________________________________________________ n = 30000; m = 100000; Dijkstra_List_priority time is 145 Dijkstra_heap time is 78 SPFA_List time is 73 The answer of SPFA_List is 91079 The answer of Dijkstra_List_priority is 91079 The answer of Dijkstra_Heap is 91079 _________________________________________________ n = 30000; m = 1000000; Dijkstra_List_priority time is 625 Dijkstra_heap time is 453 SPFA_List time is 1057 The answer of SPFA_List is 10881 The answer of Dijkstra_List_priority is 10881 The answer of Dijkstra_Heap is 10881 _________________________________________________ n = 30000; m = 3000000; Dijkstra_List_priority time is 963 Dijkstra_heap time is 940 SPFA_List time is 1762 The answer of SPFA_List is 2606 The answer of Dijkstra_List_priority is 2606 The answer of Dijkstra_Heap is 2606 _________________________________________________

分享到：