0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Eloo Nov 24 '17 at 12:05
  • $\begingroup$ 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. $\endgroup$ – user80502 Nov 24 '17 at 12:14
  • $\begingroup$ 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? $\endgroup$ – Eloo Nov 24 '17 at 18:09
  • $\begingroup$ 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]$ ? $\endgroup$ – user80502 Nov 24 '17 at 19:15
  • 1
    $\begingroup$ 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! $\endgroup$ – Eloo Nov 25 '17 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.