Dijkstra’s Shortest Path Algorithm

A pretty good implementation of Dijkstra’s shortest-path algorithm.

This implementation is designed to process large in-memory graphs. It will perform reasonably well even when the number of edges is in the millions. Using numbered indexes for nodes, rather than string labels or objects, was by design. This reduced the memory footprint needed for the graph and speeds up graph creation and lookups.

This code was adapted to Typescript/Deno from A Walkthrough of Dijkstra’s Algorithm (In JavaScript!) on Medium. This code 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. See also Dijkstra’s algorithm on Wikipedia.

Example

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 the article.

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).weights[CAFEGRUMPY],
  14,
);