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.

Directed Graphs

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

Priority Queues

Various heaps for use in Dijkstra's algorithm are provided.  These are all derived from a common base class.
The individual heap implementations are given below:
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.

Example Usage (Experiment Code)

The following example program demonstrates how to use the different heap implementations with Dijkstra's algorithm.
In addition, the following experiment code can be used to compare the different instances of Dijkstra's algorithm on different graphs.