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.
1 Answer
$\begingroup$
$\endgroup$
5
$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$.
-
$\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– Eloo2017-11-24 12:05:24 +00:00Commented Nov 24, 2017 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– user805022017-11-24 12:14:44 +00:00Commented Nov 24, 2017 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– Eloo2017-11-24 18:09:57 +00:00Commented Nov 24, 2017 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– user805022017-11-24 19:15:50 +00:00Commented Nov 24, 2017 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– Eloo2017-11-25 08:28:32 +00:00Commented Nov 25, 2017 at 8:28