| 1 | Running time tests of Dijkstra algorithm on DIMACS USA road graphs:
|
|---|
| 2 |
|
|---|
| 3 | USA-East USA-West USA-Center USA
|
|---|
| 4 | n = 3,598,623 6,262,104 14,081,816 23,947,347
|
|---|
| 5 | m = 8,778,114 15,248,146 34,292,496 58,333,344
|
|---|
| 6 |
|
|---|
| 7 | BinHeap
|
|---|
| 8 | real time: 1.37882s 2.76038s 9.2069s 13.8576s
|
|---|
| 9 | # decrease: 255,968 453,036 1,009,707 1,721,827
|
|---|
| 10 |
|
|---|
| 11 | Relative running times using different heaps:
|
|---|
| 12 |
|
|---|
| 13 | BinHeap 1 1 1 1
|
|---|
| 14 | FouraryHeap 1.0125 1.00388 0.95992 0.99249
|
|---|
| 15 | KaryHeap, K=4 1.06953 1.05834 1.00351 1.05584
|
|---|
| 16 | KaryHeap, K=8 1.10841 1.09064 1.0091 1.07601
|
|---|
| 17 | KaryHeap, K=16 1.21442 1.1885 1.07335 1.14117
|
|---|
| 18 | FibHeap 2.60177 2.49706 2.00734 2.28037
|
|---|
| 19 | PairingHeap 4.32173 4.21006 3.18253 3.61469
|
|---|
| 20 | RadixHeap 1.29437 1.25158 1.11141 1.15881
|
|---|
| 21 | BucketHeap 1.02371 1.0223 0.87654 0.87517
|
|---|
| 22 |
|
|---|
| 23 |
|
|---|
| 24 |
|
|---|
| 25 | Running time tests of Dijkstra algorithm on "worst case graphs"
|
|---|
| 26 | (for which a decrease() should be called for almost all arcs):
|
|---|
| 27 |
|
|---|
| 28 |
|
|---|
| 29 | n = 1,000 10,000 20,000
|
|---|
| 30 | m = 499,500 49,995,000 199,990,000
|
|---|
| 31 |
|
|---|
| 32 | BinHeap
|
|---|
| 33 | real time: 0.02595s 2.96707s 9.2069s
|
|---|
| 34 | # decrease: 498,501 49,985,001 199,970,001
|
|---|
| 35 |
|
|---|
| 36 | Relative running times using different heaps:
|
|---|
| 37 |
|
|---|
| 38 | BinHeap 1 1 1
|
|---|
| 39 | FouraryHeap 0.586849 0.598493 0.586294
|
|---|
| 40 | KaryHeap, K=4 0.617215 0.623449 0.60979
|
|---|
| 41 | KaryHeap, K=8 0.538696 0.511745 0.496764
|
|---|
| 42 | KaryHeap, K=16 0.500899 0.465654 0.450195
|
|---|
| 43 | KaryHeap, K=32 0.474184 0.448789 0.425124
|
|---|
| 44 | KaryHeap, K=64 0.503833 0.452305 0.433415
|
|---|
| 45 | KaryHeap, K=128 0.477954 0.415909 0.393518
|
|---|
| 46 | FibHeap 1.09494 0.999109 0.948152
|
|---|
| 47 | PairingHeap 0.911916 0.827428 0.771995
|
|---|
| 48 | RadixHeap 0.377262 0.347746 0.327151
|
|---|
| 49 | BucketHeap 0.866452 0.788165 0.777849
|
|---|
