Pathfinder algorithm written in typescript. Uses all the power of Dijkstra algorithm.
npm install dijkstra-pathfinder --save
# or
yarn add dijkstra-pathfinder
Create a graph with bidirectional arcs with graph.addArc(A, B)
.
Dot graph
graph {
rankdir=LR
A -- E -- D
A -- B -- C -- D
}
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');
const graph = new Graph();
const A = new Node();
const B = new Node();
const C = new Node();
const D = new Node();
const E = new Node();
graph.addArc(A, B);
graph.addArc(B, C);
graph.addArc(C, D);
graph.addArc(A, E);
graph.addArc(E, D);
// Instanciate a Dijkstra instance with A as starting node.
const dijkstra = new Dijkstra(graph, A);
// Calculate all best paths from A.
dijkstra.calculate();
// Path from A to D
dijkstra.getPathTo(D); // Node[] = [A, E, D]
// Path from A to C
const pathToC = dijkstra.getPathTo(C); // Node[] = [A, B, C]
Specify arc distance with graph.addArc(A, B, 3)
.
If not set, distance is set to 1
.
Dot graph
graph {
rankdir=LR
A -- E [label=3]
E -- D [label=5]
A -- B [label=2]
B -- C -- D [label=1]
}
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');
const graph = new Graph();
const A = new Node();
const B = new Node();
const C = new Node();
const D = new Node();
const E = new Node();
graph.addArc(A, B, 2);
graph.addArc(B, C, 1);
graph.addArc(C, D, 1);
graph.addArc(A, E, 3);
graph.addArc(E, D, 2);
// Instanciate a Dijkstra instance with A as starting node.
const dijkstra = new Dijkstra(graph, A);
// Calculate all best paths from A.
dijkstra.calculate();
// Path from A to D
const pathToD = dijkstra.getPathTo(D); // Node[] = [A, B, C, D]
// Distance from A to D
pathToD[pathToD.length - 1].bestPath.distance; // number = 4
// Path from A to C
const pathToC = dijkstra.getPathTo(C);
// Distance from A to C
pathToC[pathToC.length - 1].bestPath.distance; // number = 3
Use oriented arcs with graph.addOrientedArc(B, A)
.
Dot graph
digraph {
rankdir=LR
{rank = min; A}
A -> E -> D
B -> C -> D
B -> A
}
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');
const graph = new Graph();
const A = new Node();
const B = new Node();
const C = new Node();
const D = new Node();
const E = new Node();
graph.addOrientedArc(B, A);
graph.addArc(B, C);
graph.addArc(C, D);
graph.addOrientedArc(A, E);
graph.addOrientedArc(E, D);
const dijkstra = new Dijkstra(graph, A);
dijkstra.calculate();
// Path from A to D
const pathToD = dijkstra.getPathTo(D); // Node[] = [A, E, D]
// Path from A to C
const pathToC = dijkstra.getPathTo(C); // Node[] = [A, E, D, C]
Note that:
graph.addArc(A, B);
is equivalent to:
graph.addOrientedArc(A, B);
graph.addOrientedArc(B, A);
Add payload to your nodes to give them a business value:
Dot graph
graph {
rankdir=LR
A [label="A (1;1)"]
B [label="B (4;5)"]
FarFarAway [label="🏰"]
A -- B [label=5]
B -- Paris -- London -- B
London -- FarFarAway [label=40]
}
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');
const graph = new Graph();
const A = new Node('A (1;1)');
const B = new Node('B (4;5)');
const Paris = new Node('Paris');
const London = new Node('London');
const FarFarAway = new Node('🏰');
graph.addArc(A, B, 5);
graph.addArc(B, Paris);
graph.addArc(Paris, London);
graph.addArc(B, London);
graph.addArc(London, FarFarAway, 40);
const dijkstra = new Dijkstra(graph, A);
dijkstra.calculate();
// Path from A to 🏰
const pathToD = dijkstra.getPathTo(graph.findNodeByPayload('🏰'));
pathToD[0]; // Node = A
pathToD[0].payload; // string = "A (1;1)"
pathToD[1].payload; // string = "B (4;5)"
pathToD[2].payload; // string = "London"
pathToD[3].payload; // string = "🏰"
pathToD[pathToD.length - 1].bestPath.distance; // number = 46
Clone a graph instance:
Dot graph
graph {
rankdir=LR
A -- B -- C
subgraph cluster {
label=graph2
edge[style=dashed]
A -- C
}
}
const { Graph, Node, Dijkstra } = require('dijkstra-pathfinder');
const graph = new Graph();
const A = new Node('A');
const B = new Node('B');
const C = new Node('C');
graph.addArc(A, B);
graph.addArc(B, C);
const graph2 = graph.clone();
// Let's add a shortcut in cloned graph.
graph2.addArc(graph2.findNodeByPayload('A'), graph2.findNodeByPayload('C'));
// Instanciate a Dijkstra instance with A as starting node.
const dijkstra = new Dijkstra(graph, A);
dijkstra.calculate();
// Path from A to C
const path = dijkstra.getPathTo(C);
/*
Node[] = [
{payload: 'A'},
{payload: 'B'},
{payload: 'C'},
]
*/
// Instanciate another Dijkstra instance on graph2.
const dijkstra2 = new Dijkstra(graph2, graph2.findNodeByPayload('A'));
dijkstra2.calculate();
// Path from A to C
const path2 = dijkstra2.getPathTo(graph2.findNodeByPayload('C'));
/*
Node[] = [
{payload: 'A'},
{payload: 'C'},
]
*/
Graphs are generated with Dot language and this generator: https://edotor.net.
Clone this repo, then:
# Install dependencies with
yarn
# Run tests with
yarn test
# Build files with
yarn build
This library is under MIT License.