node-dijkstra

A NodeJS (or io.js) implementation of the Dijkstra's shortest path problem.

Installation

npm install node-dijkstra --save

Usage

Basic example:

var Graph = require('node-dijkstras');

var g = new Graph();

g.addVertex('A', {B:1});
g.addVertex('B', {A:1, C:2, D: 4});
g.addVertex('C', {B:2, D:1});
g.addVertex('D', {C:1, B:4});

console.log(g.shortestPath('A', 'D')); // => ['A', 'B', 'C', 'D']

API

Graph([vertices])

Parameters:

• verticies (optional): An object containing a vertices graph.

var g = new Graph();
// or
var g = new Graph({
  A: {B: 1, C: 2},
  B: {A: 1}
})

Graph.prototype.addVertex(name, edges)

Parameters:

• name: name of the vertex
• edges: object containing the connected vertices and the cost

Returns: this

var g = new Graph();

g.addVertex('A', {B:1});

// you can chain the calls
g.addVertex('B', {A:1}).addVertex('C', {A:3});

Graph.prototype.shortestPath(start, finish [, options])

Parameters:

• start: name of the starting vertex
• finish: name of the end vertex
• options: optional options object

Returns:

Array containing the crossed vertices names, in order from the starting vertex to the finish vertex, by default it includes the start and finish vertices as well. Returns null if no path can be found between the start and finish vertices.

Options:

• trim (default: false): if set to true, it won't include the starting and finish vertices in the returned path.
• reverse (default: false): if set to true, it will return the array vertices in reversed order

var Graph = require('node-dijkstras');

var g = new Graph();

g.addVertex('A', {B:1});
g.addVertex('B', {A:1, C:2, D: 4});
g.addVertex('C', {B:2, D:1});
g.addVertex('D', {C:1, B:4});

g.shortestPath('A', 'D'); // => ['A', 'B', 'C', 'D']

// trimmed
g.shortestPath('A', 'D', {trim: true}); // => [B', 'C']

// reversed
g.shortestPath('A', 'D', {reverse: true}); // => ['D', 'C', 'B', 'A']

// reversed and trimmed
g.shortestPath('A', 'D', {
  reverse: true,
  trim: true
}); // => ['C', 'B']

Testing

npm test