This package contains an efficient implementation (C++) of the edge-disjoint K-shortest paths algorithm. It comes with a python wrapper (pybind11) that allows to give the graph data through Numpy arrays.
The underlying C++ code is largely taken from here.
We give here installation instructions applicable to Ubuntu/Debian-based distributions.
- Install requirements:
sudo apt install -y graphviz cmake - Clone repository along with the pybind11 sub-module
git clone --recurse-submodules git@github.com:lejeunel/pyksp.git - Compile and install using your favorite package-manager, e.g.
cd pyksp pip install .
Go through the demo.py script to see how to interact with the module.
Most steps are commented therein.
A simple graph with 8 nodes and 13 edges, where a is the source node and z is the sink node, gives the following set of 3 edge-disjoint shortest paths:
