Dijkstra's Algorithm for the SSSP

In this lesson, we’ll study Dijkstra’s algorithm, which is the most common algorithm that efficiently solves the SSSP problem.

Explanation of Dijkstra’s algorithm

Let’s use the following example graph to execute Dijkstra’s algorithm:

We want to solve the SSSP problem starting from node $a$, which is marked in gray, meaning that it is discovered. Like in BFS, we’ll also keep track of the distance of each node to the starting vertex. In the beginning, we’ll only know the starting vertex, and its distance is $0$.

Dijkstra’s algorithm works similarly to BFS in the sense that the closest discovered, yet unexplored node is always explored first. In the beginning, we’ll need to start with node $a$, the only discovered node. We’ll mark it as black, which means “finished,” and note the distances of its neighbors.

Here, we use the notation $d(u)$ to refer to the distance of node $u$. For example, we currently have $d(b) = 6$.

The main difference compared to regular BFS is that the distances for the discovered nodes are not yet final. They can still be improved by finding a better path. A node’s distance is only fixed once it is finished and corresponds to the length of the shortest path to the node. We now must select the closest unexplored node for exploration. Since we are now working with weighted graphs, the edge weights need to be taken into consideration when choosing the closest node. Currently, the closest node is $d$, so it will be processed next. This means that we can finalize the distance of $d$ to be $4$.

From $d$, we can discover the new node $e$. We’ll also find another edge to the already discovered node $b$. Let’s check whether we need to update the distance of $b$. The currently best-known path to $b$ has length $6$. Our new path to node $b$ has a total length of $5$:

• we know that our current node $d$ has a distance of