Dijkstra's Algorithm Proof of Correctness

Theorem 24.6 (Correctness of Dijkstra’s algorithm)
Dijkstra’s algorithm, run on a weighted, directed graph G = (V, E) with non-
negative weight function w and source s, terminates with d[u] = δ(s, u) for all
vertices u ∈ V .
Proof
We use the following loop invariant:
At the start of each iteration of the while loop of lines 4–8, d[v] = δ(s, v)
for each vertex v ∈ S.
It suffices to show for each vertex u ∈ V , we have d[u] = δ(s, u) at the time
when u is added to set S. Once we show that d[u] = δ(s, u), we rely on the
upper-bound property to show that the equality holds at all times thereafter.
Initialization: Initially, S = ∅, and so the invariant is trivially true.
Maintenance: We wish to show that in each iteration, d[u] = δ(s, u) for the
vertex added to set S. For the purpose of contradiction, let u be the first vertex
for which d[u] = δ(s, u) when it is added to set S. We shall focus our attention
on the situation at the beginning of the iteration of the while loop in which u
is added to S and derive the contradiction that d[u] = δ(s, u) at that time by
examining a shortest path from s to u. We must have u = s because s is the
first vertex added to set S and d[s] = δ(s, s) = 0 at that time. Because u = s,
we also have that S = ∅ just before u is added to S. There must be some path
from s to u, for otherwise d[u] = δ(s, u) = ∞ by the no-path property, which
would violate our assumption that d[u] = δ(s, u). Because there is at least
one path, there is a shortest path p from s to u. Prior to adding u to S, path p
connects a vertex in S, namely s, to a vertex in V − S, namely u. Let us consider
the first vertex y along p such that y ∈ V − S, and let x ∈ S be y’s predecessor.

Thus, path p can be decomposed as s ❀ x → y ❀ u. Here ❀ means following path p1 on LHS and p2 on RHS.
(Either of paths p1 or p2 may have no edges.)

We claim that d[y] = δ(s, y) when u is added to S. To prove this claim,
observe that x ∈ S. Then, because u is chosen as the first vertex for which
d[u] = δ(s, u) when it is added to S, we had d[x] = δ(s, x) when x was
added to S. Edge (x, y) was relaxed at that time, so the claim follows from the
convergence property.
We can now obtain a contradiction to prove that d[u] = δ(s, u). Because y oc-
curs before u on a shortest path from s to u and all edge weights are nonnegative
(notably those on path p2 ), we have δ(s, y) ≤ δ(s, u), and thus
d[y] = δ(s, y)
≤ δ(s, u)
≤ d[u]
(by the upper-bound property) .
(24.2)
But because both vertices u and y were in V − S when u was chosen in line 5,
we have d[u] ≤ d[y]. Thus, the two inequalities in (24.2) are in fact equalities,
giving
d[y] = δ(s, y) = δ(s, u) = d[u] .
Consequently, d[u] = δ(s, u), which contradicts our choice of u. We conclude
that d[u] = δ(s, u) when u is added to S, and that this equality is maintained at
all times thereafter.
Termination: At termination, Q = ∅ which, along with our earlier invariant that
Q = V − S, implies that S = V . Thus, d[u] = δ(s, u) for all vertices u ∈ V .