Implementing Dijkstra’s Algorithm from Scratch
Apr 6, 2019
I’m continuing to review all the basic data structures and algorithms in computer science. This week I was working on graphs and graph algorithms, and it was the turn of Dijkstra’s algorithm.
As you may recall, Dijkstra’s algorithm finds a single shortest path (there may be several, but the algorithm finds only one of them) from a source vertex to all other vertices in a weighted graph. In this case, the graph can be either directed or undirected, but no negative weights are allowed.
Here’s an example of Dijkstra’s algorithm in my whiteboard.
An example of Dijkstra’s algorithm on an undirected graph. Shortest paths starting from two different sources are shown: the red lines starting from vertex W, and the dashed black lines starting from vertex R.
Dijkstra’s is a greedy algorithm, meaning that at each step, it will always choose the best possible option at that point, even though it might not be the most optimal globally. The algorithm itself is actually quite simple (and elegant), and it’s kind of amazing that it works and that it is correct (for a formal proof of the correctness of Dijkstra’s algorithm, I recommend reading chapter 24 in the 3rd edition of the Introduction to Algorithms book by Cormen et al., aka CLRS).
However, there are a few key data structures and abstractions that we must maintain in order for it to work properly. Especially if we want to keep at least $O(n^2)$ time complexity. We can improve this running time to $O(E\cdot log V)$, where E represents the set of edges and V the set of vertices in the graph, by using a binary heap as explained below.
Dijkstra's Algorithm Implementation
When I say that I implemented it from scratch, it’s because I used my own graph abstract data type (ADT) implementation, as well as my own min-heap priority queue. I used an adjacency list representation to create the graph. For the priority queue, I had previously implemented one when I was reviewing binary heaps. However, this was a max-heap. Converting it to a min-heap was only a matter of changing four > (greater than) symbols on the sift_down() and sift_up() operations. So, this only took me $O(1)$ time.
The min-heap priority queue is needed to keep track of the minimum weights (or distances) to the next vertices that are currently reachable. We must also be able to update the weights of the elements in the heap after the edge relaxation step. This turns out to be not so trivial.
However, once we have these data structures and supporting methods in place, implementing Dijkstra’s is rather straightforward.
Source Code
Here’s a link to the python source code in my GitHub page.
Final Thoughts
I have found it quite useful to go back and implement these algorithms and data structures from scratch. By doing this, I’m noting all kinds of subtleties that I’m pretty sure I missed the first time I came across these topics. It’s been truly (re)enlightening.