A fast and memory-efficient implementation of Dijkstra's shortest-path algorithm for Deno.
This implementation of Dijkstra'a algorithm is able to process large in-memory
graphs. It will perform reasonably well even with millions of edges. The
performance is O(n*log(n)), where n is proportional to the number of nodes
plus the number of edges in the graph. The use of integers to represent nodes in
the graph is intentional and actually one of the keys to its performance and
scalability.
This code was adapted to Typescript from A Walkthrough of Dijkstra's Algorithm (In JavaScript!) on Medium. This implemetation was originally part of BlackholeSuns, an open source project that allowed thousands of No Man's Sky players to navigate the galaxy using mapped black holes. This version is cleaned up a bit and includes a few bug fixes and more tests than the original. See also Dijkstra's algorithm on Wikipedia.
deno doc --reload https://deno.land/x/dijkstras_algorithm/dijkstra.tsdeno test --reloadDijkstra's algorithm calculates the shortest paths from the start node to all other nodes in the graph. All of them. In other words, it isn't just calculating one path at a time. This can let you cheaply do things like find the 20 closest nodes from a particular node in the graph, for example.
One you have loaded a graph definition into a solver, you can clone it. You can then add nodes to the cloned graph. Loading a large graph over and over takes time, and depending on overhead, this can be even slower than calculating the shortest paths. This type of reuse lets you get super-fast results.
This example recreates the example from the article referenced earlier. The
nodes are mapped to integers from 0 to n-1. The names and weights are taken
from
A Walkthrough of Dijkstra's Algorithm (In JavaScript!).
const FULLSTACK = 0;
const DIGINN = 1;
const DUBLINER = 2;
const STARBUCKS = 3;
const CAFEGRUMPY = 4;
const INSOMNIACOOKIES = 5;
const cafes = DijkstraShortestPathSolver.init(6);
cafes.addBidirEdge(DIGINN, FULLSTACK, 7);
cafes.addBidirEdge(FULLSTACK, STARBUCKS, 6);
cafes.addBidirEdge(DIGINN, DUBLINER, 4);
cafes.addBidirEdge(FULLSTACK, DUBLINER, 2);
cafes.addBidirEdge(DUBLINER, STARBUCKS, 3);
cafes.addBidirEdge(DIGINN, CAFEGRUMPY, 9);
cafes.addBidirEdge(CAFEGRUMPY, INSOMNIACOOKIES, 5);
cafes.addBidirEdge(DUBLINER, INSOMNIACOOKIES, 7);
cafes.addBidirEdge(STARBUCKS, INSOMNIACOOKIES, 6);
assertEquals(
cafes.calculateFor(FULLSTACK).shortestPathTo(CAFEGRUMPY),
[FULLSTACK, DUBLINER, INSOMNIACOOKIES, CAFEGRUMPY],
);
assertEquals(
cafes.calculateFor(FULLSTACK).weightOfPathTo(CAFEGRUMPY),
14,
);