Materials

The raw L14 slides (pdf) and here are Thu’s annotated slides.

Topics

• Dijkstra Shortest paths from a single source

Correctness proof

Dijkstra’s algoritm stays ahead and always produces shortest paths. To argue this formally, lets define the set $S$ to be the set of nodes which are not in the queue after line 5 in the algorithm (before the while loop).

At the beginning of this while loop, $S$ is empty. Thus it holds that for all nodes in $v\in S$, it holds the $d_v = \delta(s,v)$, i.e., the value $d_v$ assigned by the algorithm matches the shortest path length from $s$ to $v$.

Suppose this property holds after $i$ iterations of the while loop. We now consider the $i+1$st iteration, and let $u$ be the node that is returned from the call to ExtractMin.

• We first argue that $d_u$ at this point corresponds to the length of a path, or $\infty$ if there are no paths. This follows from the relaxation lines (9,10,11) and the initialization step when $d_u$ is set. If the value is $\infty$, then there are no paths to $u$ and thus $d_u=\delta(s,u)$ as required. Otherwise, if the value is some number, there must have been some node $z$, processed earlier, such that $d_u = \delta(s,z) + w(z,u)$ per lines 9,10,11.

• Next we consider any path $p$ from $s$ to $u$ in the graph $G$ at this point. Every such path $p$ has some edge $e=(x,y)$ in which $x\in S$ at this point, and $y \not\in S$. This follows because at this point, $u$ is not in S. The weight of this path is $$ w(p) = w_p(s,x) + w(x,y) + w_p(y,u)$$ where we abuse the notation and say $w_p(s,x)$ and $w_p(y,u)$ correpond to the weight of the portion of the path $p$ from nodes $s$ to $x$ and $y$ to $u$ respectively. Since $x\in S$, we know that $d_x = \delta(s,x)$, and therefore $$w(p) \geq d_x + w(x,y) + w_p(y,u)$$ Furthermore, at the point in the algorithm when $x$ is added to $S$, we know that the edge $w(x,y)$ is considered, and therefore, we must have that $d_y \leq d_x + w(x,y)$. Therefore, we have $$ w(p) \geq d_y + w_p(y,u)$$ Next, since node $u$ is the result of the call to ExtractMin, we also know that $d_u \leq d_y$, and therefore we have $$ w(p) \geq d_u + w_p(y,u) $$ Finally, because all of the edge weights in this graph are positive, it follows that $w_p(y,u)>0$, and thus we have that $$w(p) \geq d_u$$ which means that every path from $s$ to $u$ has weight that is at least $d_u$, which implies that $d_u = \delta(s,u)$ at the point that $u$ is removed from the queue and added to $S$, which concludes the induction.