Dijkstra’s Shortest Path

An interactive exploration of the famous Dijkstra algorithm

January 15, 2008 2 minute read

By any measures, Edsgar Wybe Dijkstra was a remarkable man - one of the worlds undisputed leading computer scientist at the end of the 20th century, inventor of an operating system called “THE”, that could have come straight from the script of one of the Airplane movies (“does it run on THE? The what? The THE.”), long term chairman of his own fictional company that he described as the “most miserable business ever conceived” and originator of the meme-phrase “[insert pet hate here] considered harmful”.

But one aspect of his work that has important historical significance is his development of algorithms. In 1959 Dijkstra published a short paper in Numerische Mathematik entitled “A Note on Two Problems in Connexion with Graphs”. Algorithms of course go right back to the earliest days of human history, but they saw a resurgence in the 1800’s through to the second world war, the invention of the modern computer all the way to the present day and our obsession with Google’s ranking algorithms. In his 1959 paper Dijkstra addressed the problem of finding the shortest route between two nodes in a graph or colloquially “how do I get from point A to point B on a map via the shortest distance”. Essentially the same problem a satnav device has to solve when you tell it where you want to go.

This is an interactive exploration of that algorithm intended to inspire interest and further reading, not a line by line exploration of the algorithm, though the code is available on github if you’d like to take that on. Sorry but this doesn’t work in IE8 or older, due to IE’s lack of support for .. well .. most things.

Let’s start with that graph. Here’s an imaginary map with five towns (nodes) on it:

Each line is of a specific length (distance). If we wish to travel from the first town (A) to the last town (E) there are a few choices. The shortest route (A -> B, B -> E) has been highlighted in red. Visually it’s hard to see why this route is shorter than A -> C, C -> E, but not mathematically.

In fact it’s ten pixels (miles) shorter. I know this because Dijkstra tells me so.

To experience some shortest-path routing for yourself try out the new improved Dijkstra Explorer available on github. You’ll just need a modern HTML 5 capable browser.

Notes

An excellent and detailed contextual study of Dijkstra’s Shortest Path can be found on the University of Melbourne’s site.
The graph node/line drawing is implemented using Mike Bostock’s spectacularly awesome D3.js
The picture, by Eli Krupitsky (Nidarus), can be found on Deviant Art and is part of a series of fridge magnets entitled ‘pioneers of computer science’.
If this has piqued your interest you might want to take a look at Dijkstra’s Shunting Yard Algorithm