A Comparison of Data Structures for Dijkstra's Single Source Shortest Path Algorithm
Shane Saunders
Department of Computer Science
University of Canterbury
Abstract
Dijkstra's algorithm computes the shortest paths between a starting vertex and each other vertex in a directed graph. The performance of Dijkstra's algorithm depends on how it is implemented. This mainly relates to the type of data structure used for the frontier set.
This honours project compares the performance of the Fibonacci heap and 2-3 heap implementations of Dijkstra's algorithm. The 2-3 heap is a new data structure invented by T. Takaoka. From the amortized analysis of heap operations, the 2-3 heap and Fibonacci heap implementations of Dijkstra's algorithm have a worst case time complexity of O(m+n log n). Here n is the number of vertices in the graph and m is the number of edges. If we consider constant factors, worst case analysis gives the number of comparisons, s, as s = 3m+1:44n log 2 n for the Fibonacci heap, and s = 2m+ 2n log 2 n for the 2-3 heap.
For random graphs, the average case performance of Dijkstra's algorithm is well within these bounds. To compare the 2-3 heap and Fibonacci heap implementations of Dijkstra's algorithm in detail, we need to consider the average case behaviour. Experimental results for average case processing time and number of comparisons, somewhat re ect the worst case analysis.
