Security News
Fluent Assertions Faces Backlash After Abandoning Open Source Licensing
Fluent Assertions is facing backlash after dropping the Apache license for a commercial model, leaving users blindsided and questioning contributor rights.
@aeolun/dijkstra-calculator
Advanced tools
Dijkstra calculator for the shortest path in a graph of nodes given a weight.
@aeolun: This is fairly seriously modified from the original to return the final weight for a route, and take into account a variety of limits like fuel
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
FAQs
Dijkstra calculator for the shortest path in a graph of nodes given a weight.
We found that @aeolun/dijkstra-calculator demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Fluent Assertions is facing backlash after dropping the Apache license for a commercial model, leaving users blindsided and questioning contributor rights.
Research
Security News
Socket researchers uncover the risks of a malicious Python package targeting Discord developers.
Security News
The UK is proposing a bold ban on ransomware payments by public entities to disrupt cybercrime, protect critical services, and lead global cybersecurity efforts.