Understanding Dijkstra's algorithm

Dijkstra's algorithm is a single-source shortest path finding algorithm that can solve this problem for graphs with non-negative edge weights. It is a generalized form of breadth-first search, using the same idea but generalizing the order of visiting nodes. The breadth-first search algorithm determines the order of nodes to visit based on their depth from the source node, whereas Dijkstra's algorithm does the same based on the distance from the source node.

The depth of a node is the minimum number of edges between itself and the source, whereas the distance is the minimum sum of edge weights between itself and the source. For an unweighted graph or a graph where all edge weights are the same, depth and distance mean the same thing and as we will see later, Dijkstra's algorithm will visit them in the same order as the breadth-first search.

Algorithm

To generalise the BFS algorithm into Dijkstra's algorithm, we use a sorted set, which is a binary search tree-based data structure, instead of a regular queue to always maintain a sorted list of nodes to visit. Instead of just the nodes, we add a pair consisting of the node and its currently known minimum distance from the source to the set, allowing us to access the pair with the minimum distance value easily.

To keep track of the shortest distance, we create a distance map and initialize it with 0 for the source node and infinite for all other nodes.

We then create a sorted set set of (distance, node) pairs, and add all the (distance, node) pairs from the distance map to the set. The set is first sorted by the first item in the pair, which is the currently known distance from the source node, and then by the node identifier itself. Since the set is sorted this way, the node with the shortest distance from the source is always at the beginning of the set.