# Dijkstra algorithm step in Introduction to Algorithms

In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d[y] with the the edge $$\omega(<x,y>) + \delta(s,x)$$, d[u] can't be smaller than delta[u], so shouldn't y be in S when we add x to S? thanks.

$u$ is supposed to be the first node to be insert in $V$ such that $d(s, u) \neq \delta(s, u)$. Before the insertion, $u$ is in $S-V$, it's clear. In addition, $y$ is supposed to be the first node in a choosen optimal path $s -> u$ to belong to $S - V$ when picking $u$ from $S - V$. So before we insert $u$ in $V$, $u$ and $y$ are both in $S - V$. Note that $y$ can be equal to $u$.
• Based on our assumption, $y$ must exist, because in the worst case, it's just $u$. If you try to find the first node that belongs to $S - V$, and you don't find any, then you can pick $u$, because $u$ don't belong to $V$ before being inserted. For the contradiction that you give, you still need the false assumption, because $x$ and $y$ have been defined thanks to this assumption. – user80502 Nov 24 '17 at 12:14
• So I gave it another thought. What we are saying is that if $d[u] = \delta(s,u)$ when we add it, then $\delta(s,u) = \delta(s,y)$ which is fine, but otherwise $\delta(s, u) < d[u] \leq d[y] = \delta(s,y)$ which is a contradiction because y is before x on the shortest path. Am I correct? – Eloo Nov 24 '17 at 18:09
• You don't have to consider $d[u] = \delta(s, u)$, because we supposed in the beginning that $d[u] \neq \delta(s, u)$. For the rest you are correct, but not for the reason you give. $y$ is before $u$ in the shortest path, and weights are positive, so $\delta(s, u) >= \delta(s, y)$. In addition, $\delta(s, u) <= d[u] <= d[y] = \delta(s, y)$, so by merging : $d[u] = d[y] = \delta(s, y)$ so $d[u] = \delta(s, u)$ which is a contradiction with the assumption we made at the beginning. But, how do we know that $d[u] <= d[y]$ and $\delta(s, y) = d[y]$ ? – user80502 Nov 24 '17 at 19:15