I don't understand the proof of correctness of Dijkstra's Algorithm
Dijkstra's Algorithm:
Proof of correctness of Dijkstra's Algorithm:
Specifically, I don't understand the second part of the proof, the part after the illustration.
I'll start with this question: Why is LSP(a,v) >= LSP(a,s) + w(s,t)? Also, what is 'r' in '...then t would be added to T instead of r'?
This is what I could come up with (but it seems to me it's unrelated to the proof above):
Posted May 12, 2026, 6:16 AM UTC
109