Expected Performance of Dijkstra's Shortest Path Algorithm

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. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR8920505. Research during a visit to M.I.T. partially supported by ARPA Contract N00013-95-1-1246. 1 Introduction The shortest path problem with nonnegative arc lengths is one of the most natural network optimization problems and occurs widely in practice. The problem is well-studied. Dijkstra's algorithm [7] is the best k..