Fast data structures for shortest path routing: a comparative evaluation

The execution time of Dijkstra´s (1959) algorithm for shortest path routing strongly depends upon the underlying priority queue data structure used to store intermediate path costs for the graph during the algorithm´s iterations. In particular, the efficiency is determined by how quickly the data structure can execute the operations of EXTRACT-MIN and DECREASE-KEY. Using Dijkstra´s algorithm on graphs of various sizes and topologies, this paper compares the actual performance of the standard implicit binary heap with that of several proposed data structures: the binomial heap, relaxed heap, run relaxed heap, Fibonacci heap and splay tree. In particular, we compare the data structures´ performance of the key operations, EXTRACT-MIN and DECREASE-KEY