# Algorithms Notes – Chapter 7

xkcd/263

Correctness – Continued

Note: An easier way to understand the following lemma is to realize that it shows that at any given time, the queue $Q$ holds at most two distinct $d$ values.

Lemma 3: Suppose during the execution of the algorithm, the queue $Q$ contains the vertices $\langle v_{1}, v_{2}, ... , v_{r} \rangle$ where $v_{1}$ is the head of the queue and $v_{r}$ is the tail. Then $v_{r}.d \le v_{1}.d + 1$ and $v_{i}.d \le v_{i+1}.d$ for $i = 1, 2, ... , r-1$.

Proof: Proof by induction on queue operations.

Basis Step: Since the queue only contains $s$ initially, the lemma is true. This completes the basis step.

Inductive Step: We need to prove that the lemma remains true after both enqueueing and dequeueing a vertex.

• Dequeueing – If $v_{1}$ was the head of the queue, now $v_{2}$ will become the head (If $v_{1}$ was the only element and hence the queue is empty now, the lemma holds vacuously). By the inductive hypothesis, $v_{1}.d \le v_{2}.d$. Also by the inductive hypothesis, $v_{r}.d \le v_{1}.d + 1$. Now since $v_{r}.d \le v_{1}.d + 1$ and $v_{1}.d \le v_{2}.d$, it is evident that $v_{r}.d \le v_{2}.d + 1$. Hence the lemma remains true.
• Enqueueing – When a vertex $v$ is enqueued in line 18 of the algorithm, it becomes $v_{r+1}$. Since we have already dequeued the vertex $u$ whose adjacency list is being scanned, it must be true that $v_{1}.d \ge u.d$ where $v_{1}.d$ is the current head of the queue. Hence $v_{r+1}.d = u.d + 1 \le v_{1}.d + 1$. Since, by the inductive hypothesis, $v_{r}.d \le u.d + 1$ and we know that $v_{r+1}.d = u.d + 1$, it is true that $v_{r}.d \le r_{r + 1}.d$. Hence the lemma remains true.

This completes the inductive step. $\square$

Corollary 1: Let $v_{i}$ and $v_{j}$ be two vertices that are enqueued during the execution of the algorithm such that $v_{i}$ is enqueued before $v_{j}$. Then $v_{i}.d \le v_{j}.d$ at the time when $v_{j}$ is enqueued.

Proof: It is evident from lemma 3 (this looks more like an assertion than a proof, I know. Blame the textbook Introduction to Algorithms by Cormen et al. not me).

xkcd/257

We are, at last, ready to prove the correctness of the Breadth-First Search algorithm. *drumroll*

Theorem (Correction of BFS):

Let $G = (V, E)$ be a directed or undirected graph. Suppose the algorithm is run on $G$ with the vertex $s$ as the source. Then

1. During its execution, the algorithm discovers every vertex $v$ in $G$ that can be reached from the source $s$ and, when the algorithm terminates, the distance of that vertex $v.d$ equals the shortest path distance from $s$ to $v$ i.e $\delta (s, v)$. and,
2. For any vertex $v$ other than the source vertex $s$ that is reachable from $s$, one of the shortest paths from $s$ to Slatex v\$ is the shortest path from $s$ to the parent of $v$: $v.\pi$ plus the edge that connects $v.\pi$ to $v$: $(v.\pi, v)$.

Proof:

Proof of 1- Proof by contradiction. Suppose a vertex $v$ receives a $d$ value such that $v.d \not= \delta(s, v)$. Since, from line 7, $s.d = 0 = \delta(s, s)$, it can be seen than $v \not= s$. By lemma 2, we know that $v.d \ge \delta(s, v)$. Since $v.d \not= \delta(s, v)$, it must be true that $v.d > \delta(s, v)$. If $v$ is not reachable from $s$, then $\delta(s, v) = \infty$ and hence it must be true that $v.d \le \delta(s, v) = \infty$, which contradicts the above statement. Hence $v$ must be a vertex that is reachable from $s$.

Let the vertex $u$ be the predecessor of $v$ on the shortest path from $s$ to $v$. Then $\delta(s, v) = \delta(s, v) + 1 = u.d + 1$. Since $v.d > \delta(s, v)$, we can infer the following inequality: $v.d > \delta(u, v) + 1$. We shall call this inequality $P$. When the vertex $u$ is dequeued by the algorithm in line 12, v can have one of the three colors: white, gray or black. We need to prove that, in all three cases, we arrive at a contradiction to inequality $P$.

1. If $v$ is white, then line 16 sets the value of $v.d$ to $u.d + 1$ which is the shortest path distance from $s$ to $v$. Hence $v.d = \delta(s, v)$, which contradicts $P$.
2. If $v$ is black then it has already been dequeued, which means it was enqueued before $u$ was enqueued. By corollary 1, this implies than $v.d \le u.d$, which contradicts $P$.
3. If $v$ is gray then it was discovered while scanning the adjacency list of some vertex $w$ which was dequeued before $u$. By corollary 1, this means that $w.d \le u.d$ and, since $w$ is the predecessor of $v$, that $v.d = w.d + 1$. Since $w.d \le u.d$, it is also true that $w.d + 1 \le u.d + 1$. Since $v.d = w.d + 1$ and $\delta(s, v) = u.d + 1$, this means that $v.d \le \delta(s, v)$, which contradicts $P$.

Hence, at the termination of the algorithm, $v.d = \delta(s, v)$ for every vertex $v$ in $G$.

Suppose there is a vertex $v$ in $G$ such that it is reachable from $s$ but not discovered by the algorithm. Then $v.d = \infty$ and hence $v.d > \delta(s, v)$. But we already established that $v.d = \delta(s, v)$ hence this is a contradiction. Therefore all vertices that are reachable from $s$ are discovered by the algorithm. $\square$

Proof of 2- If $v.\pi = u$, then $v.d = u.d + 1$. Therefore we can obtain a shortest path from $s$ to $v$ by taking the shortest path from $s$ to $v.\pi$ and then moving along that edge $(v.\pi, v)$. $\square$

And voila, we have proved that the Breadth-First Search algorithm is correct. (whew, I’m exhausted. You’re welcome.)