Question

Prove the correctness of dijkstra's algorithm using induction.

Answer 1

This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).
The proof makes a case that considering path pp is the shortest path that connects a vertex in set SS(set of vertices where the distance of nodes to node ss, the starting node, is minimal) to a vertex in set uu in V−SV−S. It then considers the first vertex as yy in set V−SV−S along the path pp. It argues that y.d≤u.dy.d≤u.d which is intuitive as yy precedes uu in set V−SV−S. The second argument that since both uu and yy were in V−SV−S when uu was chosen thus u.d≤y.du.d≤y.d. I have following two doubts about the second argument:

Why were yy and uu both in V−SV−S when uu was chosen? We know by our construction that when both uu and yy are in V−S



plzzzzzzzz add brainlist