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 shortest path (there may be several, but the algorithm finds only one of them) from a single 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.
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 𝘖(𝑛²) time complexity. We can improve this running time to O(E 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.
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.
Here’s the python implementation on my GitHub page:
I have found 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.
References:
¹ Dijkstra’s Algorithm on Wikipedia, aka the source of all human knowledge :)
