A comparison of worst case performance of priority queues used in Dijkstra's shortest path algorithm
A.W. Vickers · UC Research Repository (University of Canterbury) · 1986
This report presents results of experiments comparing the worst case performance of Dijkstra's Single Source Shortest Path algorithm using different priority queues. A description and worst case analysis are given of the five priority queues which were considered.These were an array of keys, array of pointers, binary heap, alpha heap and Fibonacci heap. To produce worst case performance of Dijkstra's algorithm it was necessary for the author to design a method for generating graphs which would induce this behaviour. A family of graphs with this property was discovered and their description is given within. Results of applying Dijkstra's algorithm to graphs of this type, using each of the priority queues are listed in the appendix while the more interesting outcomes are graphed and analysed in the main body of the report.