An interactive exploration of the famous Dijkstra algorithm
permalinkJanuary 15, 2008
I originally published this in August last year but it's become so popular that it needed a sprucing up for the new year. This new version takes 30% off the load time, has better instructions, and generally looks nicer than the old one. The Dijkstra algorithm works out the shortest route from A to B on any given map of connected nodes. It's essentially what your car sat nav does with map data. What's significant about Dijkstra's Algorithm is that it was one of the first modern computing problems to be solved, published and, eventually, taken seriously. It's not overly complicated, although coming up with such an elegant solution is, of course, a mark of genius in itself.
Instructions
Enter Nodes
First, you need to set the number of nodes (towns) in the problem space. There's a limit of seven for this demo, otherwise the graphical rendering gets a bit CPU intensive. Then click the draw table button to construct the input form for the distances between the towns.
Enter Distances
The input table takes the distance in pixels between nodes (towns). You'll notice that half of the boxes are greyed out. Don't worry about this, it's just to make entry simpler - the distance from node 2 to node 5 is the same as the distance from node 5 to node 2 so when you fill in one distance the table automatically fills in the reverse distance.
So just enter the distance between relevant nodes (you might want to play with a few variations to get the idea of how distances/connections map onto the graphical plan) and click the show plan button when you're ready.
Working it out
The 'Shortest Path' calculation will be done on the basis that you wish to get from node "0" to the last node in your dataset. You can click the show plan button as many times as you like, updating values between clicks. If you want to start again then just click the clear table button. If a route is found you'll be told the path through the nodes plus the total distance. If your end node isn't reachable from 'node 0' then a 'no path found' message will be shown.
Quirks
Don't create big maps then leave this page open in your browser overnight. Because of the way the animation is done it can start to hog all your CPU. If you notice this then just clear the table or close the window. I'll get around to fixing this when I have time.
There's a limited amount of sense checking done on your distances. You can assign nonsensical or zero distances between nodes which will make the plan do strange things - unconnected towns will fly off the map, and contradicting distances will make the map bounce and do odd things, but this is unrelated to the calculations. Click show plan for a town with no distances at all and you'll see what I mean.
And finally, have fun. I wrote this for fun myself over a couple of wet lunchtimes after reading about Edsger Dijkstra and some of his pioneering work in the area of algorithm development.
Node Data
Distance Data
Visualisation and Results
Credits
Dijkstra
Main credit, of course, goes to the main himself, Edsger Dijkstra.
Calculation Script
The implementation of the shortest path algorithm comes from a link I found on Wikipedia. It was the only client-side version I could find, and I wanted the whole thing to be 'local' so adapted this from the original to be more readable, and self-contained.
Bouncy Balls
The bouncy ball drawing thing is based on JSViz, a forcedirected and snowflake drawing javascript package developed by Kyle Scholz, Lorien Henrywilkins and Alistair Rutherford.
Dynamic HTML
The table drawing code is based on scriptaculous and although much of the rest of it was rather thrown together, any elegant, syntactically sugary, bits are due to the marvellous team behind Prototype.