ngraph.path

You can install the module via npm or use a CDN for browser-based projects.

npm:

npm i ngraph.path

CDN:

<script src="https://unpkg.com/ngraph.path@1.6.1/dist/ngraph.path.umd.js"></script>

If using the CDN, the library is available under the global name ngraphPath.

To find a path between two nodes in an unweighted graph, use the aStar finder. This is equivalent to Dijkstra's algorithm. The find method returns an array of nodes representing the path. If no path is found, it returns an empty array.

let path = require('ngraph.path');
let pathFinder = path.aStar(graph); // graph is an ngraph.graph instance

let fromNodeId = 40;
let toNodeId = 42;
let foundPath = pathFinder.find(fromNodeId, toNodeId);
// foundPath is array of nodes in the graph

You can prevent the pathfinder from using certain links by providing a blocked function in the options. The blocked function receives (fromNode, toNode, link) and should return true if the path is blocked.

let pathFinder = path.aStar(graph, {
  blocked(fromNode, toNode, link) {
    return link.data.disruption;
  },
});
let result = pathFinder.find('NYC', 'Washington');

To treat the graph as oriented (where links have a specific direction), set the oriented option to true in the finder options.

let pathFinder = aStar(graph, {
  oriented: true
});

To speed up the search, you can provide a heuristic function. This function 'guesses' the distance between the current node and the target.

Important: The heuristic must not overestimate the actual distance between nodes, otherwise the algorithm cannot guarantee the shortest path.

Options:

• distance(fromNode, toNode): The actual cost to move between nodes.
• heuristic(fromNode, toNode): The estimated cost from the current node to the target.

let pathFinder = aStar(graph, {
  distance(fromNode, toNode) {
    let dx = fromNode.data.x - toNode.data.x;
    let dy = fromNode.data.y - toNode.data.y;
    return Math.sqrt(dx * dx + dy * dy);
  },
  heuristic(fromNode, toNode) {
    let dx = fromNode.data.x - toNode.data.x;
    let dy = fromNode.data.y - toNode.data.y;
    return Math.sqrt(dx * dx + dy * dy);
  }
});
let path = pathFinder.find('NYC', 'Washington');

To find the shortest path based on edge weights, provide a distance function in the options object passed to aStar. The distance function receives (fromNode, toNode, link) and should return the weight of the link.

let pathFinder = aStar(graph, {
  distance(fromNode, toNode, link) {
    return link.data.weight;
  }
});
let path = pathFinder.find('a', 'd');

The library provides several A* based finders. All finders implement the .find(fromNodeId, toNodeId) method.