A Comparison of Data Structures for Dijkstra's Single Source Shortest Path Algorithm
Degree GrantorUniversity of Canterbury
Degree NameBachelor of Science with Honours
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 0( 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₂ n for the Fibonacci heap, and s = 2m + 2n log₂ 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 reflect the worst case analysis.
SubjectsField of Research::08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics::080201 - Analysis of Algorithms and Complexity
- Engineering: Reports