dijkstra-pathfinder

Dijkstra Pathfinder

Pathfinder algorithm written in typescript. Uses all the power of Dijkstra algorithm.

Install

npm install dijkstra-pathfinder --save

# or

yarn add dijkstra-pathfinder

Usage

Basic graph

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]

Graph with distances between nodes

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

Oriented arcs

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 your payload

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 graph

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.

Develop

Clone this repo, then:

# Install dependencies with
yarn

# Run tests with
yarn test

# Build files with
yarn build

License

This library is under MIT License.