Skip to content

Latest commit

 

History

History
25 lines (25 loc) · 1.99 KB

dijkstra-comparison.md

File metadata and controls

25 lines (25 loc) · 1.99 KB
Graph Random graph gen. duration (s) Minimum heap Dijkstra duration (s) Fibonacci heap Dijkstra duration (s)
10000000 nodes, 0-2 edges (avg/2) 11.52395 64.7737 136.019
1000000 nodes, 0-10 edges (avg/10) 4.55533 8.01175 7.97475
100000 nodes, 0-100 edges (avg/10) 4.29613 1.69952 1.82649
10000 nodes, 0-1000 edges (avg/10) 3.97784 0.960649 0.982903
5000 nodes, 1000-4999 edges (avg/10) 14.2962 2.65765 2.64545
1000 nodes, 0-5 edges (avg/1000) 0.00164839 0.00278834 0.00419505
1000 nodes, 5-25 edges (avg/1000) 0.00837044 0.00515332 0.00626651
1000 nodes, 25-50 edges (avg/1000) 0.0198723 0.00823139 0.00949376
1000 nodes, 50-100 edges (avg/1000) 0.0396748 0.0133738 0.014895
1000 nodes, 100-250 edges (avg/1000) 0.0957135 0.0278096 0.0296473
1000 nodes, 250-500 edges (avg/1000) 0.221025 0.0577536 0.0592843
1000 nodes, 500-999 edges (avg/100) 0.54739 0.107992 0.109876
1000 nodes, 800-999 edges (avg/100) 0.734475 0.124516 0.126086
10000 nodes, 0-5 edges (avg/100) 0.0181426 0.0340005 0.0468139
10000 nodes, 5-25 edges (avg/100) 0.0934201 0.0611416 0.0705779
10000 nodes, 25-50 edges (avg/100) 0.239676 0.0994511 0.111735
10000 nodes, 50-100 edges (avg/100) 0.512049 0.164474 0.178736
10000 nodes, 100-250 edges (avg/10) 1.26146 0.337311 0.359589
10000 nodes, 250-500 edges (avg/100) 2.78104 0.670178 0.691743
10000 nodes, 500-1000 edges (avg/5) 5.82262 1.32221 1.33883
10000 nodes, 1000-2500 edges (avg/5) 13.6814 3.11661 3.11721
10000 nodes, 2500-5000 edges (avg/3) 30.2975 6.56225 6.53865
10000 nodes, 5000-9999 edges (Bo1) 166.906 23.1221 14.8138