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 try variations on this for yourself, first choose the number of nodes (towns) you’d like in your graph (map). The minimum is 3, maximum 20.
Number of nodes :
With a table in place, it’s now a case of entering the distances between nodes. Duplicate (i.e. reverse routes) are blanked out to make filling in the distances easier.
Then choose a start and an end node and simply click ‘find route’ to draw the graph and find the shortest path.
Play around with the distances, and the start and end points, and the graph will update itself automatically. Have fun.
If this has piqued your interest you might want to take a look at Dijkstra’s Shunting Yard Algorithm