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.
mkdir build && cd build
cmake ..
make -j <n-jobs>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 2make tests -j <n-jobs>
./tests/tests -s