Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

Question

I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked with $\dagger$

Theorem: (Correctness of breadth-first search)

Let $G = (V, E)$ be a directed or undirected graph, and suppose that $BFS$ is run on $G$ from a given source vertex $s \in V$. Then, during its execution, $BFS$ discovers every vertex $v \in V$ that is reachable from the source $s$, and upon termination, $d[v] = \delta(s, v)$ for all $v \in V$. Moreover, for any vertex $v \neq s$ that is reachable from $s$, one of the shortest paths from $s$ to $v$ is a shortest path from $s$ to $\pi[v]$ followed by the edge $(\pi[v], v)$.

$\left[ \delta(s,v) \rightarrow \text{Length of the shortest path from s to v}\\ d[v]\rightarrow \text{distance assigned to vertex $v$ from $s$ by BFS}\\\pi[v]\rightarrow \text{Predecessor of $v$ in the path from $s$ to $v$ in the BFS}\right]$

Proof:

Assume, for the purpose of contradiction, that some vertex receives a $d$ value not equal to its shortest path distance. Let $v$ be the vertex with minimum $\delta(s, v)$ that receives such an incorrect $d$ value; clearly $v \neq s$. We know $d[v] \geq \delta(s, v)$, and thus we have that $d[v] > \delta(s, v)$. Vertex $v$ must be reachable from $s$, for if it is not, then $\delta(s, v) = \infty \geq d[v]$. Let $u$ be the vertex immediately preceding $v$ on a shortest path from $s$ to $v$, so that $\delta(s, v) = \delta(s, u) + 1$. Because $\delta(s, u) < \delta(s, v)$, and because of how we chose $v$ , we have $d[u] = \delta(s, u)$$^\dagger$. Putting these properties together, we have

$d[v] > \delta(s, v) = \delta(s, u) + 1 = d[u] + 1 $

(The proof then continues, but I do not include the rest here...)

I could not understand the reasoning behind the statement marked with $\dagger$, $\text{"because of how we chose $v$ , we have $d[u] = \delta(s, u)$"}$

Answer 1

It is perhaps more illuminating to reformulate this proof by contradiction as a proof by induction. We prove that $d[v] = \delta(s,v)$ by induction on the latter (the case $\delta(s,v) = \infty$ should be taken care of separately). If $\delta(s,v) = 0$ then $v = s$, and indeed $d[s] = 0$. Now suppose that the result holds for all vertices at distance $i$ from $s$, and consider a vertex $v$ at distance $i+1$ from $s$. Let $u$ be a neighbor of $v$ at distance $i$ from $s$. By induction, $d[u] = \delta(s,u)$, and so once $u$ is processed, $d[v] \leq \delta(s,u) + 1 = \delta(s,v)$. Since $d[v] \geq \delta(s,v)$, it follows that $d[v] = \delta(s,v)$, as needed.

How do the two proofs relate? Let $U$ be the set of vertices such that $d[v] = \delta(s,v)$; clearly $s \in U$. Let $v \neq s$ be an arbitrary vertex reachable from $s$, and let $u$ be a predecessor of $v$, that is, a neighbor of $v$ such that $\delta(s,v) = \delta(s,u) + 1$. The proof shows that if $u \in U$ then also $v \in U$. You can now proceed in two different ways:

• Proof by contradiction: choose $v \in U$ minimizing $\delta(s,v)$. By definition, the predecessor of $v$ does lie in $U$, and so we reach a contradiction.
• Proof by induction: we show that all vertices reachable from $s$ are in $U$, by induction on their distance from $s$.

The two proofs are equivalent. I prefer the second.