Proving that the distance values extracted in Dijkstra's algorithm is non-decreasing?
- by Gail
I'm reviewing my old algorithms notes and have come across this proof. It was from an assignment I had and I got it correct, but I feel that the proof certainly lacks.
The question is to prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.
My proof goes as follows:
Proof by contradiction. Fist, assume
that we pull a vertex from Q with
d-value 'i'. Next time, we pull a
vertex with d-value 'j'. When we
pulled i, we have finalised our
d-value and computed the shortest-path
from the start vertex, s, to i. Since
we have positive edge weights, it is
impossible for our d-values to shrink
as we add vertices to our path. If
after pulling i from Q, we pull j with
a smaller d-value, we may not have a
shortest path to i, since we may be
able to reach i through j. However,
we have already computed the shortest
path to i. We did not check a
possible path. We no longer have a
guaranteed path. Contradiction.
