Shortest path with Dijkstra by Justin Bozonier.
From the post:
Tonight I decided my study time would be to sit down and implement Djikstra’s algorithm in Python to help me understand it. When coding up a solution to a problem like this I tend to try to not look at other solutions so I won’t be tempted to cheat and skip steps in the learning process. Hopefully that means a more thorough explanation as well as code that makes more sense to someone just learning.
So first what is a “shortest path” algorithm and why Djikstra’s algorithm specifically?
Shortest path algorithms can be most easily related to a class of problem every online driving direction service (like MapQuest or Google Maps) has to solve. These problems work with a concept known as a directed weighted graph which is a collection of points with connections to other points as well as a cost for each connection. Here, it might help to visualize it:
One of the more fundamental graph algorithms.
Take special note:
I also instrumented my code to explain each step of the algorithm here (settle in, it’s gonna be a long one): https://gist.github.com/jcbozonier/5424843
I first saw this at DZone.