Use this to find the shortest path of nodes in graph using Dijkstra's algorithm. Learn how to pronounce Dijkstra here.
This library a TypeScript port from Alfred Gatsby @Prottoy2938 for the great work done here: https://gist.github.com/Prottoy2938/66849e04b0bac459606059f5f9f3aa1a
At Ditto we do a lot of imagery with react-force-graph to show how our mesh network can establish virtual connections between peers. This library is used to aid in showing the shortest path between peers. Note: we use a modified version of Dijkstra's Algorithm with differing priority per link as a consideration for our system. This library is primarily used for assisting in simple visualizations in our documentation and blog.
Use either npm
or yarn
to install the library. This library is targeting ES5 and can be run on either Web, Node, or Electron projects. It does not have any dependencies.
npm install dijkstra-calculator
# or if you're using yarn
yarn add dijkstra-calculator
Let's say you want to find the shortest path between two nodes in the graph.
Given a series of Nodes in a graph with identifiers "A "
to "F"
and edges established between each one
import { DijkstraCalculator } from 'dijkstra-calculator';
const graph = new DijkstraCalculator();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'E');
graph.addEdge('C', 'D');
graph.addEdge('C', 'F');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
// Now you can calculate the shortest distance between A and E
const path = graph.calculateShortestPath('A', 'E');
// this will print ['A', 'B', 'E']
There are instances where you'd like to add some priority or weight to an edge. The 3rd parameter
import { DijkstraCalculator } from 'dijkstra-calculator';
const graph = new DijkstraCalculator();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);
const path = graph.calculateShortestPath('A', 'E');
// with consideration of the weights at the edge, the values will be ['A', 'C', 'D', 'F', 'E']
Libraries like d3 or Vis.js or force-graph will want a structure to specify edges that looks something like this:
[
{ source: 'A', target: 'B' },
{ source: 'C', target: 'D' },
// etc...
];
You can get something that fits these APIs by calling calculateShortestPathAsLinkedListResult
like below:
const linkedList = graph.calculateShortestPathAsLinkedListResult('A', 'E')
// This will result in `linkedList` with the following contents
[
{ source: 'A', target: 'C' },
{ source: 'C', target: 'D' },
{ source: 'D', target: 'F' },
{ source: 'F', target: 'E' },
];
Not sure how to pronounce Dijkstra? https://www.youtube.com/watch?v=lg6uIPSvclU
Generated using TypeDoc