Shortest Path Algorithms in C++

Shortest Path Algorithms and Priority Queues in C++

This secondary repository contains C++ implementations of shortest path algorithms and the priority queues that they use. A standard implementation of Dijkstra's algorithm is provided which is able to use the various priority queues interchangeably.

A downloadable package containing all these source files is provided.
[Download]

Directed Graphs

A standard implementation of directed graphs is used by Dijkstra's algorithm.

directed graphs: dgraph.cpp dgraph.h

Priority Queues

Various heaps for use in Dijkstra's algorithm are provided. These are all derived from a common base class.

heap base class: heap.h

The individual heap implementations are given below:

Fibonacci heap
fheap.cpp fheap.h

2-3 heap
heap23.cpp heap23.h

trinomial heap
triheap.cpp triheap.h

extended trinomial heap (with O(1) worst-case time for decrease-key operations)
triheap_ext.cpp triheap_ext.h

radix heap
radixheap.cpp radixheap.h
(description)

Since the radix heap works specifically with Dijkstra's algorithm, it is described separately from the other heaps. A description of other heaps can be found in the heaps section of the main algorithm repository.

Dijkstra's Algorithm

Dijkstra's algorithm was implemented with the ability to use any of the above heaps.

Dijkstra's algorithm: dijkstra.cpp dijkstra.h

Example Usage (Experiment Code)

The following example program demonstrates how to use the different heap implementations with Dijkstra's algorithm.

directed graph generation: dgraph_factory.cpp dgraph_factory.h
main program: run_dijkstra.cpp

In addition, the following experiment code can be used to compare the different instances of Dijkstra's algorithm on different graphs.

directed graph providers: dgraphp.h dgraphp_lib.h
experiment: exp_sp.cpp exp_sp.h
main program: run_exp.cpp