KSP - K Shortest Path
Yen's algorithm.
Computes the K shortest paths in a graph from node S to node T usingInstallation
npm i k-shortest-path
How to use
This package needs graphlib to work.
first install graphlib using:
npm i graphlib
or follow the latest instructions on their official github
now build your graph:
const graphlib = ; let g = ; // draw example graph as the image aboveg;g;g;g;g;g;g;g;g;
and finally use this library to calculate k shortest path:
const ksp = ; // (graph, startNode, targetNode, k)ksp; /* return 3 paths:[ { "totalCost": 5, "edges": [ { "fromNode": "C", "toNode": "E", "weight": 2 }, { "fromNode": "E", "toNode": "F", "weight": 2 }, { "fromNode": "F", "toNode": "H", "weight": 1} ] }, { "totalCost": 7, "edges": [ { "fromNode": "C", "toNode": "E", "weight": 2 }, { "fromNode": "E", "toNode": "G", "weight": 3 }, { "fromNode": "G", "toNode": "H", "weight": 2 } ] }, { "totalCost": 8, "edges": [ { "fromNode": "C", "toNode": "D", "weight": 3 }, { "fromNode": "D", "toNode": "F", "weight": 4 }, { "fromNode": "F", "toNode": "H", "weight": 1 } ] }]*/
for more complex graphs there are two optional parameters:
ksp.ksp(g, 'C', 'H', 3, weightFunc, edgeFunc);
weightFunc
edgeFunc
they are exactly the same like in graphlib dijkstra.
Information & limitations
- Yen's algorithm computes loop-less paths only
- This Yen's algorithm use Dijkstra algorithm for finding the shortest path on each iteration, therefor works only with non-negative weights.
Credits
Thanks to Brandon Smock for implement Yen's algorithem on Java, Helped me a lot.
Tested with Node version v10.16.3