Implementation of Dijkstra

Implementation notes

As we saw in the previous lesson, Dijkstra’s algorithm is very similar to BFS in the sense that the closest unexplored node is processed next within the order of processing. However, determining the closest node needs to consider the distance estimates known so far, and that they can change over time. Therefore, it is not possible to simply store the unfinished nodes in a static queue data structure.

A naive implementation could simply store the currently known distance of each node in a vector and check all the unexplored nodes during each iteration to get the node with the minimum distance. However, this would lead to a time complexity of $\mathcal{O}(|V|^2)$, and we can do better.

Instead, we should use a data structure that allows us to efficiently get the node with the lowest distance estimate. Additionally, the data structure should support updating the distance estimate of a vertex. Both properties can be fulfilled by using a priority queue data structure to store the nodes and their distances.

The following illustration shows how such a priority queue looks during the execution of Dijkstra’s algorithm:

Each element of the priority queue contains a vertex together with its currently known distance estimate. The elements of the queue are ordered by their distances. In priority queue terminology, the distance is called the key of the queue element, and elements are always ordered by their keys. When a new node is inserted or the distance of an existing node is updated, the elements of the queue are reordered to maintain the ordering of the element keys.

For example, if we relax an edge and update the distance of $w$ to $5$, the priority queue would look like this:

Under the hood, priority queues are often implemented using binary heaps. They only need logarithmic time to insert new elements, update existing elements, or extract the minimum element.

Priority queues in C++

The C++ standard template library contains std::priority_queue, which is an implementation of priority queues. However, there is a major downside to this class: it does not support updating the key of an element, an operation that we need for relaxing edges in Dijkstra’s algorithm.

We could implement our own priority queue data structure that supports decreasing keys, but this would be both challenging and time-consuming. Thankfully, there are viable workarounds.

One option is to use a std::set container as the queue, which supports extraction, insertion, and deletion operations in logarithmic time. Together with some bookkeeping, we can update elements by first deleting them and then inserting their updated ...