Algorithms Notes – Chapter 7

certainty

xkcd/263

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 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).

code_talkers

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.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s