Edge-disjoint K-shortest-paths in C++

Implementation

We implement the edge-disjoint K-shortest paths algorithm, which internally leverages Bellman–Ford, and Dijkstra algorithms. The former serves as a pre-conditioning step to transform the graph from (possibly) negative weighted edges to non-negatives, and is implemented using topological sort for efficiency. The latter is implemented using a binary heap.

Installation

mkdir build && cd build
cmake ..
make -j <n-jobs>

Usage

As a quick example, we provide an example graph coded in a human-readable DOT file. Run the algorithm on example.dot using source node 0, sink node 5, and retrieve 2 optimal edge-disjoint paths using:

./build/edksp examples/example.dot 0 5 2

Testing

make tests -j <n-jobs>
./tests/tests -s