Algorithms
There are three main groups of algorithms in this API: Dijkstra, shortest-cycle, and k-paths.
There are two main groups of algorithms in this API: Dijkstra and k-paths.
Dijkstra
This is a variation on the standard Dijkstra’s algorithm (see references 1, 3, and 4 for algorithmic details). It efficiently calculates the shortest path from a source to a destination or to all destinations. The DJK package’s implementation includes support for the following:
- client-defined just-in-time edge-consideration (via a callback that accepts or rejects edges for a path)
- client-defined just-in-time path-consideration (via a callback that accepts or rejects a candidate path)
- hop-limits, returning shortest paths that do not exceed
Hedges - retrieval of all equal-cost shortest-paths
- retrieval of the first-found shortest path
Shortest-Cycle
These algorithms for edge-disjoint and vertex-disjoint pairs of shortest-paths (and maximal approximations thereto) are based on algorithms found in reference 2. Recall that a cycle is a pair of paths with a common source and destination.
The four types of cycles in this API are:
- vertex-disjoint
- maximally (approximately) vertex-disjoint
- edge-disjoint
- maximally (approximately) edge-disjoint
“Maximally vertex-disjoint shortest pair” is a pair of minimal total cost among pairs that have the fewest intersecting vertices.
“Maximally edge-disjoint shortest pair” is a pair of minimal total cost among pairs that have the fewest intersecting edges.
K-Paths
This algorithm is based on Dijkstra’s algorithm, but sacrifices some of its efficiency in order to support flexibility, including:
- Arbitrary number of shortest-paths (not necessarily equal-cost)
- Client-defined path-acceptability filter (via callbacks)