Dijkstra's Algorithm: Correctness Proof

The Induction Strategy

We prove Dijkstra’s algorithm terminates with $v.d = \delta(s, v)$ for all vertices $v$. The proof uses induction on the size of set $S$ (vertices whose distances have been finalised by extraction from the priority queue).

Loop invariant $\Phi$: At the start of each while-loop iteration, for every vertex $v \in S$, we have $v.d = \delta(s, v)$. That is, all vertices extracted so far have their correct shortest-path distances.

Initialisation

Before the first iteration, $S = \emptyset$, so $\Phi$ holds vacuously. The distance estimates are initialised: $s.d = 0 = \delta(s,s)$, and all other $v.d = \infty \ge \delta(s,v)$. The upper-bound property (analogous to BFS Lemma 2) holds: $v.d$ never underestimates the true distance.

The Convergence Property of RELAX

A supporting lemma used inside the proof:

Convergence Property: If $s \leadsto u \to v$ is a shortest path from $s$ to $v$, and $u.d = \delta(s, u)$ before the edge $(u, v)$ is relaxed, then $v.d = \delta(s, v)$ after the relaxation.

Proof: After relaxing $(u, v)$: $v.d \le u.d + w(u, v) = \delta(s, u) + w(u, v) = \delta(s, v)$ But we also have the upper-bound property $v.d \ge \delta(s, v)$ at all times. Therefore $v.d = \delta(s, v)$ exactly.

In words: if we already know the correct distance to $u$, and $(u, v)$ is the last edge on a true shortest path to $v$, then relaxing that edge pins down $v$‘s correct distance.

Maintenance: Proof by Contradiction

Assume the invariant fails at some point. Let $u$ be the first vertex for which $u.d \neq \delta(s, u)$ when it is added to $S$.

• $u \neq s$, since $s.d = 0 = \delta(s, s)$ (correct).
• There is a shortest path from $s$ to $u$, because if $u$ were unreachable, $u.d = \infty = \delta(s, u)$, which would be correct.
• $S \neq \emptyset$ at the moment $u$ is selected (it contains at least $s$).

Consider any shortest path $p = s \leadsto u$. Let $y$ be the first vertex along $p$ (starting from $s$) that is not yet in $S$ at the moment $u$ is selected. Let $x \in S$ be $y$‘s immediate predecessor on $p$. Decompose:

$p = s \underset{p_1}{\leadsto} x \to y \underset{p_2}{\leadsto} u$

Since $x$ was added to $S$ before $u$, and $u$ is the first vertex where the invariant fails, we know $x.d = \delta(s, x)$. When $x$ was added to $S$, the edge $(x, y)$ was relaxed. By the convergence property:

$y.d = \delta(s, y)$

Now, because all edge weights are non-negative, and $y$ appears before $u$ on a shortest path: $\delta(s, y) \le \delta(s, u)$

Because $u$ was the vertex with minimum $d$ value selected from the priority queue, and $y \notin S$ as well: $u.d \le y.d$

Chaining these inequalities: $\delta(s, u) \ge \delta(s, y) = y.d \ge u.d$

But the upper-bound property gives $u.d \ge \delta(s, u)$. Together: $u.d = \delta(s, u)$

This contradicts the assumption that $u.d$ was incorrect. Therefore the invariant $\Phi$ is maintained.

Why Non-Negative Weights Are Essential

The inequality $\delta(s, y) \le \delta(s, u)$ relies on the fact that all edges on $p_2$ (from $y$ to $u$) have non-negative weight. If any edge on $p_2$ were negative, the path $y \leadsto u$ could have negative total weight, making $\delta(s, y) \le \delta(s, u)$ false (it’s possible that $u$ is reachable from $y$ with a negative total, making $\delta(s, y) > \delta(s, u)$). This is why Dijkstra fails on graphs with negative edges: the greedy choice of minimum $d$ is no longer guaranteed to be optimal.

Termination

When the while loop exits, the priority queue $Q$ is empty. Since $Q = V \setminus S$, all vertices are now in $S$. The invariant $\Phi$ holds for all $v \in V$, so $v.d = \delta(s, v)$ for every vertex. The algorithm is correct.

The Predecessor Subgraph Is a Tree

Because RELAX sets $\pi[v] = u$ whenever a shorter path through $u$ is found, and the final $d$ values equal the true distances, the predecessor subgraph $G_\pi$ (edges $(\pi[v], v)$ for $v \neq s$) is a shortest-path tree rooted at $s$: a directed tree where the unique path from $s$ to any vertex is a shortest path in $G$.

Summary of Proof Structure

Step	Method
Invariant	$v.d = \delta(s,v)$ for all $v \in S$
Base	$S = \emptyset$, true vacuously
Assumption for failure	Let $u$ be first vertex added to $S$ with $u.d \neq \delta(s,u)$
Construct counter-path	$s \leadsto x \to y \leadsto u$ where $x \in S$, $y \notin S$
Key facts used	Convergence property; non-negative weights; $u.d \le y.d$
Contradiction	$\delta(s,u) \ge \delta(s,y) = y.d \ge u.d$, so $u.d = \delta(s,u)$
Conclusion	No first failure → invariant holds for all

Past paper questions: y2023p1q9 (bidirectional variant correctness), y2024p1q9 (relaxed costs and optimality).