0
$\begingroup$

I'm studying Breadth-First Search (BFS) from the CLRS book and I'm having trouble understanding the proof that each distance from the source node calculated by BFS is the shortest distance from the source node.

The book presents three lemmas to prove this:

Lemma 1: For any edge $(u, v) \in E$ in a graph $G = (V, E)$, the shortest distance from the source node $s$ to node $v$ is bounded by: δ(s,v)≤δ(s,u)+1

Lemma 2: The distance calculated by BFS from the source node $s$ to node $v$ is an upper bound on the shortest distance: v.d≥δ(s,v)

Lemma 3: During the execution of BFS, the queue contains nodes in the order $<v_1, v_2, v_3, ..., v_r>$, and the following properties hold: 𝑣 𝑟 . 𝑑 ≤ 𝑣 1 . 𝑑 + 1 and 𝑣 𝑖 . 𝑑 ≤ 𝑣 𝑖 + 1 . 𝑑

Proof by Contradiction: Suppose, for the sake of contradiction, that $v.d > \delta(s, v)$. Then, there exists a node $u$ preceding $v$ in the shortest path from $s$ to $v$. The book asserts that $\delta(s, u) = u.d$. My question is: how can we be sure that the shortest distance $\delta(s, u)$ is equal to the BFS distance $u.d$?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
0
$\begingroup$

The idea is as follows: The BFS algorithm propagates like a wave on the given graph, starting from the source vertex. By design, you must visit all the vertices that are at a distance of $d$ from the source before visiting any vertex that is at a distance $d+1$. This property is ensured by the FIFO nature of the Queue which is used to decide the order in which a new vertex is visited.

Now suppose a vextex $v$ is wrongly labelled. That is, the labelled distance $v.d$ is not equal to the actual distance $d = \delta(s,v)$. Now let us take help from mathematical induction here and assume that all vertices that are at distance $d-1$ have been correctly labelled. This trivially and correctly holds for the source vertex. Now, by design, we would have discovered $v$ from one of its neighbors, say $u$, which is at distance $d-1$. Thus, we would have correctly labelled $v.d = u.d + 1 = (d-1)+1 = d$. Here you also need to argue that $v$ cannot have been labelled before the vertices at level $d-1$ and no vertex of distance larger than or equal to $d$ can appear before we discover $v$ from $u$ and enqueue it. This argument is bit handweiving to convey the basic feel of the proof. The formal ones are given in the books.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.