Implementation of Dijkstra’s Single-Source Shortest-Paths in JavaScript

I’m working on a project where the client wants a cool sliding navigation effect. We’re implementing this with JavaScript/AJAX/DHTML.

One of the constraints is that pages can only be reached via certain other pages. For example, if you’re on the /portland/contact page and want to go to the /seattle/contact page, you’ll first slide up to /portland, then over to /seattle, then finally down to /seattle/contact.

After a while, it occurred to me that there were some similarities with another project I’ve been working on off and on for the last few years,, which is a bicycle trip planner a la Google Maps.

I had written a Python version of Dijkstra’s Single-Source Shortest-Paths (SSSP) for That’s available on Bitbucket as Dijkstar (so named because it also does has the potential to do A*). I figured it wouldn’t be too hard to port the Python version to JavaScript, and it wasn’t.

There were a few snags, though. Most of it was just syntactic and semantic differences between the two languages. The biggest issue was that I use “heapq“ in the Python version to maintain the costs to previously visited nodes in sorted order. JavaScript has no priority queue implementation that I could find, so I came up with a different solution that involves updating an Object (AKA hash) with costs to newly visited nodes and sorting the keys to pick the next node to visit. I’m assuming/hoping the underlying sort implementation is highly optimized.

Interestingly, I think I found at least one bug in the Python version, although I’ve been using that version for a couple years now with no known problems, so it must only be applicable in certain edge (no pun intended) cases (or maybe it’s due to some difference in the languages–need to take a closer look). I think the JS version came out cleaner, too.

If anyone’s interested, I’m releasing this under an MIT license. You can get it from here. Note that it depends on the util module that you can get from here. The util module contains some other Python-inspired JavaScript, in particular a couple of functions for generating namespaces and classes. I might write another post about that at some point.

3 thoughts on “Implementation of Dijkstra’s Single-Source Shortest-Paths in JavaScript

  1. If performance becomes an issue you may want to replace your generic sort routine (qsort?) with a d-heap. It’s been 15 years since I last coded a heap from scratch, but I recall that even in C binary heaps aren’t too bad to implement and O(1) insertions are pretty darn near impossible to beat, especially for building up big search trees one node at a time like A* does.

  2. Hi Wyatt!

    Thanks for the excellent script. I am also applying it to a bike route planner in Budapest, and in normal browsers it works really fine, however in IE8 it throws the following error, which I could not solve.

    Üzenet: A várt elem szám (number expected)
    Sor: 58
    Karakter: 7
    Kód: 0
    URI: dijkstra.js

    This is the line:
    key = keys.sort(sorter)[0];

    I hope you will have some ideas, because I am getting mad :)

    Thanks again for the nice work.

  3. Mystery is solved: I needed to add “return” within the sorter function…
    FF was smarter, for sure :)

Comments are closed.