# Question about labeling in Dijkstra's Proof of Correctness

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

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

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]$.
• 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. – aelguindy Nov 1 '16 at 22:30