Abstract for HONS 07/99 - Computer Science and Software Engineering - University of Canterbury - New Zealand
HONS 07/99

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.

  • Phone: +64 3 369 2777
    Fax: +64 3 364 2569
    CSSEadministration@canterbury.ac.nz
  • Computer Science and Software Engineering
    University of Canterbury
    Private Bag 4800, Christchurch
    New Zealand
  • Follow us
    FacebookYoutubetwitterLinked In