Correctness of Dijkstra’s Algorithm

Statement:

Dijkstra’s algorithm, run on a weighted, directed graph G = (V, E) with nonnegative weight function w and source s, terminates with u.d = 𝛿(s,u) for all vertices u ∈ V.

Analyzing the Statement:

Given: 1. G = (V, E) is a directed graph
2. G has nonnegative weight function w
3. Dijkstra’s algorithm runs on G with the source s.

To prove: Dijkstra’s algorithm terminates with u.d = 𝛿(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, v.d = 𝛿(s,v) for each vertex v ∈ S

Initialization

Initially, S is empty and hence loop invariant trivially holds.

---

Maintenance

To prove: u.d = 𝛿(s,u) when each vertex u is being added to the set S.

Note: Text given in gray like this is not a part of the proof, but given for your understanding alone – giving subtitle to each section of proof.

1. Assumption for Contradiction

(Proof by contradiction) Assume that there are vertices which for which u.d ≠ 𝛿(s,u) when it is being added to the set S.

W.l.o.g, let us assume that u is the first vertex with u.d ≠ 𝛿(s,u) added to S.

2. Splitting Cases

Case 1: There is no path from ‘s’ to ‘u’

If there is no path from s to u, then by no path property, u.d = 𝛿(s,u) = ∞, which is a contradiction to our assumption that u.d ≠ 𝛿(s,u).

---

Case 2: There is at least one path from ‘s’ to ‘u’

3. First Claim

Claim: u≠ s.

Proof of the claim: ‘s’ is the first vertex, and we already know that s.d = 𝛿(s, s) = 0. Hence the claim.

4. Decomposing shortest path

Since there is at least one path from ‘s’ to ‘u’, there is a shortest-path, say ‘p’ from ‘s’ to ‘u’. Note all vertices in path ‘p’ need not lie in the set S.

Let ‘y’ be the first vertex in path ‘p’ that is not in set S. Then the predecessor of ‘y’ in ‘p’ will be in S (since ‘y’ is the first vertex in path p not is S), we will, for convenience refer to it as ‘x’.

Then we can decompose the path as

Where p1 is the path from s to x and p2 is the path from y to u,

Note that p1 or p2 may or may not have edges.

5. Second claim

Claim 2: When u is being added to ‘s’, y.d = 𝛿(s, y)

Proof of claim: Observe that since

1. x ∈ S
2. u is the first vertex with u.d ≠ 𝛿(s,u) added to S

we had x.d = 𝛿(s, x) and while examining G.Adj[x], the edge (x, y) was relaxed at that time and hence the claim, i.e., y.d = 𝛿(s, y).

6. Third Claim

Claim 3: u.d ≤ y.d

Since u was selected to be included in S before y it follows that u.d ≤ y.d.

7. Fourth Claim

Claim 4: y.d ≤ u.d

y.d = 𝛿(s, y) (By Claim 2)
≤ 𝛿(s, u) (Since u comes after y in the shortest path)
≤ u.d (By the upper-bound property)

8. The contradiction

Combining claims 3 and 4, we have u.d ≤ y.d ≤ 𝛿(s, y) ≤ 𝛿(s, u) ≤ u.d.

Thus, we can conclude that y.d = 𝛿(s, y) = 𝛿(s, u) = u.d.

And that contradicts our choice of u. Hence we conclude that u.d = 𝛿(s, u) when ‘u’ is added and the loop invariant is maintained at all times.

Termination

At termination, Q = V – S = { }. That is, V = S. Hence, we can conclude that u.d = 𝛿(s, u) for every vertex u in V.

Hence the proof.

Pages: Contents … << Previous 8 Next Page>>