Running time tests of Dijkstra algorithm on DIMACS USA road graphs:

                   USA-East    USA-West  USA-Center      USA
n =              3,598,623   6,262,104  14,081,816  23,947,347
m =              8,778,114  15,248,146  34,292,496  58,333,344

BinHeap
   real time:      1.37882s    2.76038s    9.2069s     13.8576s
   # decrease:      255,968     453,036   1,009,707   1,721,827

Relative running times using different heaps:

BinHeap            1           1           1           1
FouraryHeap        1.0125      1.00388     0.95992     0.99249
KaryHeap, K=4      1.06953     1.05834     1.00351     1.05584
KaryHeap, K=8      1.10841     1.09064     1.0091      1.07601
KaryHeap, K=16     1.21442     1.1885      1.07335     1.14117
FibHeap            2.60177     2.49706     2.00734     2.28037
PairingHeap        4.32173     4.21006     3.18253     3.61469
RadixHeap          1.29437     1.25158     1.11141     1.15881
BucketHeap         1.02371     1.0223      0.87654     0.87517



Running time tests of Dijkstra algorithm on "worst case graphs"
(for which a decrease() should be called for almost all arcs):


n =                  1,000       10,000       20,000
m =                499,500   49,995,000  199,990,000

BinHeap
   real time:      0.02595s     2.96707s      9.2069s
   # decrease:      498,501   49,985,001  199,970,001

Relative running times using different heaps:

BinHeap           1            1            1
FouraryHeap       0.586849     0.598493     0.586294
KaryHeap, K=4     0.617215     0.623449     0.60979
KaryHeap, K=8     0.538696     0.511745     0.496764
KaryHeap, K=16    0.500899     0.465654     0.450195
KaryHeap, K=32    0.474184     0.448789     0.425124
KaryHeap, K=64    0.503833     0.452305     0.433415
KaryHeap, K=128   0.477954     0.415909     0.393518
FibHeap           1.09494      0.999109     0.948152
PairingHeap       0.911916     0.827428     0.771995
RadixHeap         0.377262     0.347746     0.327151
BucketHeap        0.866452     0.788165     0.777849