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

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)"}$$

• "Let 𝑣 be the vertex with minimum $\delta(s,v)$, that receives such an incorrect value $d$". I.e., for all $u$ such that $\delta(s,u) < \delta(s,v)$, we have $d[u] = \delta(s,u)$. – user114966 Jul 28 '20 at 9:10
• @Dmitry I do not get the intuition, for me it seems the same thing as written in the text. Might be it is quite simple but I am unable to share the same view as you do. Can you please elaborate it? – Abhishek Ghosh Jul 28 '20 at 10:02
• @AbhishekGhosh The vertex $u$ has a smaller $\delta$ than $v$, since $\delta(s,v)=\delta(s,u)+1>\delta(s,u)$. The vertex $v$ was chosen to be a vertex that, among the vertices with wrong $d$, has smallest $\delta$. Since $u$ has a smaller $\delta$ than $v$, then $u$ cannot have a wrong $d$. – plop Jul 28 '20 at 10:17
• @plop aah now I get it.. Thanks for the help. $\text{The way the vertex$v$is chosen}$ , from this line I was trying to correlate the choosing of $v$ by the $BFS$ algorithm. But they are actually pointing to the assumption they made in choosing $v$ for the proof. My though was wrong (now that I see) because $BFS$ does not choose a vertex. Once again thanks for the help... – Abhishek Ghosh Jul 28 '20 at 10:25
• The proof can also be reformulated as induction on $\delta(s,v)$. – Yuval Filmus Jul 28 '20 at 13:46

## 1 Answer

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.

• Thanks for the help. – Abhishek Ghosh Jul 28 '20 at 15:21