2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ "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)$. $\endgroup$ – Dmitry Jul 28 '20 at 9:10
  • $\begingroup$ @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? $\endgroup$ – Abhishek Ghosh Jul 28 '20 at 10:02
  • 1
    $\begingroup$ @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$. $\endgroup$ – plop Jul 28 '20 at 10:17
  • $\begingroup$ @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... $\endgroup$ – Abhishek Ghosh Jul 28 '20 at 10:25
  • 1
    $\begingroup$ The proof can also be reformulated as induction on $\delta(s,v)$. $\endgroup$ – Yuval Filmus Jul 28 '20 at 13:46
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the help. $\endgroup$ – Abhishek Ghosh Jul 28 '20 at 15:21

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.