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.
A standard implementation of directed graphs is used by Dijkstra's
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 was implemented with the ability to use any of the
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
instances of Dijkstra's algorithm on different graphs.