|Data Structures and Algorithms|
|Proof of Dijkstra's Algorithm|
We use a proof by contradiction again. But first, we assert the following Lemma:
Shortest paths are composed of shortest paths.
The proof of this is based on the notion that if there was a shorter path than any sub-path, then the shorter path should replace that sub-path to make the whole path shorter.
If s ->..-> u -> v is a shortest path from s to v, then after u has been added to S and relax(u,v,w) called, then d[v] = delta(s,v) and d[v] is not changed thereafter. For formal proofs, see Cormen or any one of the texts which cover this important algorithm.
Proof follows from the fact that at all times d[v] >= delta(s,v).
Denote the distance of the shortest path from s to u as delta(s,u). After running Dijkstra's algorithm, we assert that d[u] = delta(s,u) for all u.
Note that once u is added to S, d[u] is not changed and should be delta(s,u).
Suppose that u is the first vertex added to S
for which d[u] != delta(s,u).
Let s -(p1)-> x -> y -(p2)-> u be the shortest path
from s to u.
Where x is within S and y is the first vertex not within S.
When x was inserted into S, d[x] = delta(s,x) (since we hypothesise that u was the first vertex for which this was not true).
Edge (x,y) was relaxed at that time, so that
d[y] = delta(s,y)
Now both y and u were in V-S when u was chosen, so d[u] <= d[y].
Thus the two inequalities must be equalities,
d[y] = delta(s,y) = delta(s,u) = d[u]
So d[u] = delta(s,u) contradicting our hypothesis.
Thus when each u was inserted, d[u] = delta(s,u).
|Continue on to Huffman Encoding||Back to the Table of Contents|