Expected Performance of Dijkstra's Shortest Path Algorithm

Abstract:

We show that the expected number of decrease-key operations
in Dijkstra's shortest path algorithm is O(n log (1+m/n)) for an
n-vertex, m-arc graph. The bound holds for any graph structure;
the only assumption we make is that for every vertex, the lengths
of its incoming arcs are drawn independently from the same distribution.
The same bound holds with high probability. This result explains the
small number of decrease-key operations observed in practice and helps
to explain why Dijkstra codes based on binary heaps perform better than
ones based on Fibonacci heaps.