Expected Performance of Dijkstra's Shortest Path Algorithm
Report ID: TR-530-96Author: Tarjan, Robert E. / Goldberg, Andrew V.
Date: 1996-10-00
Pages: 7
Download Formats: |Postscript|
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.