本文主要是介绍最短路各种算法 稠密图 稀疏图 时间分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分别有下面这几种算法（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
_________________________________________________
这篇关于最短路各种算法 稠密图 稀疏图 时间分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
