# 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$.

• Ah, but I don't understand why such a y should exist based on our false assumption. That is, it seems that you can lead to the same contradiction without the false assumption, proving that you'll add y before x to S.
– Eloo
Commented Nov 24, 2017 at 12:05
• 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
Commented Nov 24, 2017 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
Commented Nov 24, 2017 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
Commented Nov 24, 2017 at 19:15
• Ah, the first one, because we add u before y, the second one, because we already added x and relaxed <x,y>, and this is corollary from a previous lemma because x is on the shortest path to y, and <x,y> completes it. Thanks a lot!
– Eloo
Commented Nov 25, 2017 at 8:28