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


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