Implementing Dijkstra's algorithm

The implementation of the original form of Dijkstra's algorithm is quite complicated and not very efficient. This is because it relies on updating values in place in a sorted set, which requires searching, deleting and then reinserting the value. A more efficient implementation of Dijkstra's algorithm uses a priority queue and adds the (distance, node) pairs to it during the graph exploration.

In this lesson, we will learn a slightly modified version of Dijkstra's algorithm, which is easier to implement and is the most widely used version.

Algorithm

We start by creating a distance map to keep track of the shortest distance for every node from the source node, and initialize it with 0 for the source node and infinite for all other nodes.