Implementation of Dijkstra's Single Source Shortest Path algorithm for directed graphs using different priotity queues (notably Fibonacci and Binomial Heaps).
The make folder contains a Makefile to build on Linux.
The vs folder contains a Visual Studio solution to build on Windows.
The generated program is ssp (ssp.exe on Windows).
ssp can be used either to generate the shortest route from every source to every destination on a given graph, or to test the performance of the different queues on random graphs of different densities.
./ssp -is file_name
runs Dijkstra's Single Source Shortest Path algorithm using an unsorted queue as priority queue.
./ssp -ib file_name
runs Dijkstra's Single Source Shortest Path algorithm using a Binomial Heap as priority queue.
./ssp -if file_name
runs Dijkstra's Single Source Shortest Path algorithm using a Fibonacci Heap as priority queue.
Alternatively
./ssp -r
runs Dijkstra's Single Source Shortest Path algorithm on a set of random graphs with different densities using for each priority queue and outputs the performance of each. The output format looks as follows:
Number of vertices Density Simple scheme(msec) F-heap scheme (msec) B-heap scheme(msec)
1001 10% 69464.000000 50349.000000 45607.000000
1001 20% 94291.000000 74725.000000 70161.000000
1001 30% 114225.000000 97229.000000 90580.000000
1001 40% 141640.000000 130986.000000 120526.000000
1001 50% 169564.000000 155323.000000 148056.000000