Analysis of Breadth-First Search
Correctness – Continued
Note: An easier way to understand the following lemma is to realize that it shows that at any given time, the queue holds at most two distinct values.
Lemma 3: Suppose during the execution of the algorithm, the queue contains the vertices where is the head of the queue and is the tail. Then and for .
Proof: Proof by induction on queue operations.
Basis Step: Since the queue only contains 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 was the head of the queue, now will become the head (If was the only element and hence the queue is empty now, the lemma holds vacuously). By the inductive hypothesis, . Also by the inductive hypothesis, . Now since and , it is evident that . Hence the lemma remains true.
- Enqueueing – When a vertex is enqueued in line 18 of the algorithm, it becomes . Since we have already dequeued the vertex whose adjacency list is being scanned, it must be true that where is the current head of the queue. Hence . Since, by the inductive hypothesis, and we know that , it is true that . Hence the lemma remains true.
This completes the inductive step.
Corollary 1: Let and be two vertices that are enqueued during the execution of the algorithm such that is enqueued before . Then at the time when 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).
We are, at last, ready to prove the correctness of the Breadth-First Search algorithm. *drumroll*
Theorem (Correction of BFS):
Let be a directed or undirected graph. Suppose the algorithm is run on with the vertex as the source. Then
- During its execution, the algorithm discovers every vertex in that can be reached from the source and, when the algorithm terminates, the distance of that vertex equals the shortest path distance from to i.e . and,
- For any vertex other than the source vertex that is reachable from , one of the shortest paths from to Slatex v$ is the shortest path from to the parent of : plus the edge that connects to : .
Proof of 1- Proof by contradiction. Suppose a vertex receives a value such that . Since, from line 7, , it can be seen than . By lemma 2, we know that . Since , it must be true that . If is not reachable from , then and hence it must be true that , which contradicts the above statement. Hence must be a vertex that is reachable from .
Let the vertex be the predecessor of on the shortest path from to . Then . Since , we can infer the following inequality: . We shall call this inequality . When the vertex 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 .
- If is white, then line 16 sets the value of to which is the shortest path distance from to . Hence , which contradicts .
- If is black then it has already been dequeued, which means it was enqueued before was enqueued. By corollary 1, this implies than , which contradicts .
- If is gray then it was discovered while scanning the adjacency list of some vertex which was dequeued before . By corollary 1, this means that and, since is the predecessor of , that . Since , it is also true that . Since and , this means that , which contradicts .
Hence, at the termination of the algorithm, for every vertex in .
Suppose there is a vertex in such that it is reachable from but not discovered by the algorithm. Then and hence . But we already established that hence this is a contradiction. Therefore all vertices that are reachable from are discovered by the algorithm.
Proof of 2- If , then . Therefore we can obtain a shortest path from to by taking the shortest path from to and then moving along that edge .
And voila, we have proved that the Breadth-First Search algorithm is correct. (whew, I’m exhausted. You’re welcome.)