1
$\begingroup$

I am trying to understand the proof of correctness for Dijkstra's algorithm (shown below) and also at the following link: CS Auskland

Proof by contradiction

Suppose that $u$ is the first vertex added to $S$ for which $d[u] \ne \delta(s,u)$. We note:

$u$ cannot be $s$, because $d[s] = 0$.

There must be a path from $s$ to $u$. If there were not, $d[u]$ would be infinity.

Since there is a path, there must be a shortest path.

When $x$ was inserted into $S$, $d[x] = \delta(s,x)$ (since we hypothesise that u was the first vertex for which this was not true).

Edge $(x,y)$ was relaxed at that time, so that $$d[y] = \delta(s,y) \le \delta(s,u) \le d[u]$$

Now both $y$ and $u$ were in $V-S$ when u was chosen, so $d[u] \le d[y]$.

How can we say that $d[u] \le d[y]$? And why aren't we saying that $d[u] \ge d[y]$? Wouldn't the label on $u$ be larger if it is further down the path from $y$?

Thus the two inequalities must be equalities, $$d[y] = \delta(s,y) = \delta(s,u) = d[u]$$

So $d[u] = \delta(s,u)$ contradicting our hypothesis.

Thus when each $u$ was inserted, $d[u] = \delta(s,u)$.

$\endgroup$
2
$\begingroup$

Since the algorithm at each step adds to $S$ the vertex with the lowest "d" value, and $y$ is not in $S$, $d[u] \leq d[y]$.

$\endgroup$
  • $\begingroup$ So, since u was selected and y was not yet in S, we're assuming that d[u] is less than d[y]? But since y is before u on the path from s to u, then d[y] <= d[u]; resulting in the contradiction? $\endgroup$ – Gary Nov 1 '16 at 22:27
  • $\begingroup$ Since u was selected and not y, d[y] cannot be greater than d[u], since if it were, the algorithm would choose y before u, but that cannot be the case since y is not in S. So since $d[u] \leq d[y]$, if you follow the inequalities on the description you linked to, you will end up deriving that $d[u] = \delta(s, u)$ contradicting the assumption that they are not equal. $\endgroup$ – aelguindy Nov 1 '16 at 22:30

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.