Dijkstra’s Algorithm

Main idea

Given a weighted digraph $G$, the algorithm works so that throughout its execution, vertices of $G$ remain conceptually partitioned into two sets $M$ and its complement $M^C = V−M$, as shown in the following figure.

Initially, the set $M$ is empty so that all vertices of $G$ are in its complement $M^C$. In each round, we repeat the following steps:

1. We pick a vertex $v$ in $M^C$ with the smallest $v.dist$ value (amongst all vertices in $M^C$) and add it to $M$.

   Note: The first vertex added to M is the source vertex since it’s the only vertex whose $dist$ attribute is initialized to $0$ instead of $\infty$.

2. With each vertex added to $M$, we perform an edge-relaxation for all the edges originating at that vertex.

Once all vertices are added to the set $M$, we consider the lengths of the shortest paths and the parent pointers correctly computed in the $v.dist$ and $v.parent$ attributes for each vertex $v$.