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:


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$.
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?
In answer to both of your questions:
  Firstly, note that during the maintenance phase of the loop invariant proof, we are in the process of inserting u into S, and the way that y is defined is that it is a node in V\S while this is happening, therefore u and y exist in V\S at the same time when u is inserted. This answers your first question.
  Secondly, note that in the proof, we assume that u.d ≠ δ(s,u). It therefore follows that there would be a pair of nodes x and y (such that π(y)=x such that x ∈ S and y ∈ V\S) such that y ≠ u and therefore y must come before u, because otherwise from the Convergence Property it would automatically follow that u.d = δ(s,u) which would be a contradiction to our assumption. Therefore from here it must follow that y comes before u. But note that from the first point I made above, y must come after u. And this is exactly the whole point of the proof, both of these things cannot happen simultaneously unless y.d = δ(s,y) = δ(s,u) = u.d.
Note that we used the assumption that u is not the minimal distance from s when added to S by showing that we reach a contradiction if we assume this.