Security News
PyPI’s New Archival Feature Closes a Major Security Gap
PyPI now allows maintainers to archive projects, improving security and helping users make informed decisions about their dependencies.
@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.
The npm package @aeolun/dijkstra-calculator receives a total of 3 weekly downloads. As such, @aeolun/dijkstra-calculator popularity was classified as not popular.
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
PyPI now allows maintainers to archive projects, improving security and helping users make informed decisions about their dependencies.
Research
Security News
Malicious npm package postcss-optimizer delivers BeaverTail malware, targeting developer systems; similarities to past campaigns suggest a North Korean connection.
Security News
CISA's KEV data is now on GitHub, offering easier access, API integration, commit history tracking, and automated updates for security teams and researchers.