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…