Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-530-96

Authors:

Date:

September 1996

Pages:

7

Download Formats:

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.