Package Exports

dijkstra-pathfinder

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (dijkstra-pathfinder) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

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).

Graph picture basic example

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.

Graph picture distances example

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).

Graph picture oriented example

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:

Graph picture payload example

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:

Graph picture clone example

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.