KSP - K Shortest Path

Computes the K shortest paths in a graph from node S to node T using Yen's algorithm.

Installation

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 = require('graphlib');

let g = new graphlib.Graph();

// draw example graph as the image above
g.setEdge('C', 'D', 3);
g.setEdge('C', 'E', 2);
g.setEdge('D', 'F', 4);
g.setEdge('E', 'D', 1);
g.setEdge('E', 'F', 2);
g.setEdge('E', 'G', 3);
g.setEdge('F', 'G', 2);
g.setEdge('F', 'H', 1);
g.setEdge('G', 'H', 2);

and finally use this library to calculate k shortest path:

const ksp = require('k-shortest-path');

// (graph, startNode, targetNode, k)
ksp.ksp(g, 'C', 'H', 3);

/* 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