# Correctness of Dijkstra's algorithm

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 $p$ is the shortest path that connects a vertex in set $S$ (set of vertices where the distance of nodes to node $s$, the starting node, is minimal) to a vertex in set $u$ in $V-S$. It then considers the first vertex as $y$ in set $V-S$ along the path $p$. It argues that $y.d \leq u.d$ which is intuitive as $y$ precedes $u$ in set $V-S$. The second argument that since both $u$ and $y$ were in $V-S$ when $u$ was chosen thus $u.d \leq y.d$. I have following two doubts about the second argument:

1. Why were $y$ and $u$ both in $V-S$ when $u$ was chosen? We know by our construction that when both $u$ and $y$ are in $V-S$, then $y$ will be chosen before $u$.
2. The node $u$ is chosen such that when it's added to set $S$ it is not at the minimum distance from node $s$. How is this used in this proof?
• It seems that the question will be hard to answer without possession of the (admittedly common) textbook. Perhaps you should ask your TA instead of here. – Yuval Filmus Dec 2 '16 at 16:25
• Here's the proof listed serverbob.3x.ro/IA/DDU0150.html As in cormen – invartraders Dec 3 '16 at 3:49
• But because both vertices u and y were in V - S when u was chosen in line 5, we have d[u] ≤ d[y].? How do we know that when both u and y was in set V-S the vertex chosen is u and not y? Where is the fact that node u when added to set S, it is not at the minimum distance from start node s utilized? Please help – invartraders Dec 3 '16 at 3:49