Repository files navigation

A fast and memory-efficient implementation of Dijkstra's shortest-path algorithmfor Deno.

This implementation of Dijkstra'a algorithm is able to process large in-memorygraphs. It will perform reasonably well even with millions of edges. Theperformance isO(n*log(n)), wheren is proportional to the number of nodesplus the number of edges in the graph. The use of integers to represent nodes inthe graph is intentional and actually one of the keys to its performance andscalability.

This code was adapted to Typescript fromA Walkthrough of Dijkstra's Algorithm (In JavaScript!)on Medium. This implemetation was originally part ofBlackholeSuns, an open source projectthat allowed thousands of No Man's Sky players to navigate the galaxy usingmapped black holes. This version is cleaned up a bit and includes a few bugfixes and more tests than the original. See alsoDijkstra's algorithm onWikipedia.

deno doc --reload https://deno.land/x/dijkstras_algorithm/dijkstra.ts

denotest --reload

Dijkstra's algorithm calculates the shortestpaths from the start node toall other nodes in the graph. All of them. In other words, it isn't justcalculating one path at a time. This can let you cheaply do things like find the20 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 canthen add nodes to the cloned graph. Loading a large graph over and over takestime, and depending on overhead, this can be even slower than calculating theshortest paths. This type of reuse lets you get super-fast results.

This example recreates the example from the article referenced earlier. Thenodes are mapped to integers from0 ton-1. The names and weights are takenfromA Walkthrough of Dijkstra's Algorithm (In JavaScript!).

constFULLSTACK=0;constDIGINN=1;constDUBLINER=2;constSTARBUCKS=3;constCAFEGRUMPY=4;constINSOMNIACOOKIES=5;constcafes=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,);