Data Structures, Algorithms, & Applications in C++
Chapter 16, Exercise 43

(a)

Define the length of a (directed) path to be the number of edges on it. Let d(v,w) be the length of a shortest (directed) path from v to w in G. d(v,v) = 0 and for every vertex w reachable from v, d(v,w) < n, where n is the number of vertices in G. We shall prove the theorem by contradiction. Suppose that the pseudocode of Figure 17.17 does not label some vertex i for which d(v,i) < n. Let j be an unlabeled vertex with minimum d(v,j). Clearly, d(v,j) < n. We may assume that d(v,j) > 0 as d(v,j) = 0 only if j = v and v is labeled right in the beginning.

Since d(v,j) > 0, there is a vertex t adjacent to j for which d(v,t) = d(v,j) - 1. By assumption, vertex t is labeled by the time breadth first search terminates. So, t must have been added to the queue at some time. Since the queue is empty at termination, t must have been deleted from the queue at some time. Immediately following this deletion, the as yet unlabeled vertices adjacent from t get labeled. Therefore, vertex j must be labeled when the pseudocode terminates. This contradicts the assumption that j is unlabeled when the pseudocode terminates.

(b)

By the time the execution of dfs completes, there is no newly labeled vertex that has an unlabeled vertex adjacent from it. As a result, there are no unlabeled vertices reachable from v. Hence all reachable vertices have been labeled label.