BFS Shortest Path Proof (Unweighted Graphs)

What is a "Shortest Path" in an Unweighted Graph?

First, let's be precise. In an unweighted graph, all edges are considered equal. Therefore, the "length" of a path is simply the number of edges it contains. The "shortest path" between two vertices, a source s and a destination t, is the path from s to t that consists of the minimum possible number of edges.

Let's formally denote the length of a true shortest path from a vertex u to a vertex v as $\delta (u,v)$. If v is unreachable from u, then $\delta (u,v)=\infty$.

When we run BFS from a source s, we can modify the algorithm slightly to store the distance from s to every other vertex it discovers. Let's call the distance computed by BFS d[v]. Our goal is to prove that for every vertex v reachable from s, d[v] = δ(s, v).

The Intuition: Level-by-Level Discovery

Before diving into the formal proof, let's reinforce the intuition. BFS explores the graph in expanding layers of distance from the source s:

• Level 0: s itself.
• Level 1: All vertices at distance 1 from s.
• Level 2: All vertices at distance 2 from s.
• And so on...

Because the algorithm completely processes all vertices at level k before discovering any vertex at level k+1, it seems logical that the first time we encounter any vertex v, it must be via a path of the shortest possible length. Any "shortcut" to v would have necessarily passed through a vertex at an earlier level, meaning v itself would have been discovered sooner.

Professor Erik Demaine from MIT provides a concise explanation of this property.

The Formal Proof

To turn this intuition into a rigorous proof, we need to establish two key properties (lemmas). We'll follow the structure presented in the lecture notes from UC Berkeley's CS 170 course, which offers a very clean and formal argument.

The proof relies on an important property of the queue during a BFS traversal.

Lemma 1: The Queue Property (Monotonicity of Distances)

The first step is to prove that as BFS runs, the vertices in the queue are ordered by their distance from the source s in a very specific way.

Let's summarize the argument for this lemma. We can prove by induction that the following invariant holds true at any step of the algorithm: if v1, v2, ..., vr are the vertices currently in the queue, then dist[v1] <= dist[v2] <= ... <= dist[vr], and furthermore, dist[vr] <= dist[v1] + 1.

• Base Case: Initially, the queue only contains s with dist[s] = 0. The invariant holds.
• Inductive Step: Assume the invariant holds. When we dequeue v1, its neighbors w1, w2, ... that have not been visited are enqueued. Their distance is set to dist[v1] + 1. The new queue is v2, ..., vr, w1, w2, ....
  • Since dist[v2] >= dist[v1], we have dist(neighbor of v1) = dist[v1] + 1 >= dist[v2].
  • From the invariant, we knew dist[vr] <= dist[v1] + 1. The newly added nodes all have this distance.
  • Therefore, the queue remains sorted by non-decreasing distance, and the difference between the minimum and maximum distance is still at most 1.

This lemma is crucial because it implies that BFS processes vertices in an orderly fashion, finishing all vertices at distance k before moving on to most vertices at distance k+1.

Lemma 2: Correctness of d[v]

Now we are ready to prove the main theorem: that the distance d[v] computed by BFS is indeed the true shortest path distance $\delta (s,v)$. The proof proceeds by induction on the distance.

Let's walk through this elegant proof together.

Proof by induction on the shortest path distance k = δ(s, v):

• Base Case (k=0): The only vertex v with $\delta (s,v)=0$ is s itself. The BFS algorithm initializes d[s] = 0 and s is the first vertex processed. So the statement holds for k=0.

• Inductive Hypothesis (IH): Assume that for all vertices u with $\delta (s,u)\le k$, the BFS algorithm correctly computes `d[u] = \delta(s, u)).

• Inductive Step: We must show that for any vertex w with $\delta (s,w)=k+1$, BFS computes d[w] = k+1.

  1. Since $\delta (s,w)=k+1$, there must exist a true shortest path s -> ... -> v -> w. On this path, v is the predecessor of w. This means $\delta (s,v)=k$.
  2. By our Inductive Hypothesis, BFS correctly computed the distance to v, so d[v] = \delta(s, v) = k.
  3. Because d[v] = k, at some point BFS will dequeue v. When it does, it will examine all of v's neighbors, including w. If w has not been visited yet, BFS will set d[w] = d[v] + 1 = k + 1. If w has been visited, its distance d[w] must already be set to some value.
  4. This shows that BFS finds a path of length k+1, so we know d[w] <= k+1. But could d[w] be less than k+1?
  5. Let's assume for the sake of contradiction that d[w] < k+1. This would mean d[w] <= k. If d[w] was set, it must have been discovered from a predecessor, let's call it v'. Then d[w] = d[v'] + 1. This implies d[v'] = d[w] - 1 < k.
  6. So, we have found a path s -> ... -> v' -> w with a total length of d[v'] + 1, which is less than k+1. This contradicts our initial premise that the shortest path distance to w, $\delta (s,w)$, is k+1.
  7. Our assumption in step 5 must be false. Therefore, d[w] cannot be less than k+1.

Since we have shown that d[w] <= k+1 and d[w] is not less than k+1, we must have d[w] = k+1. This completes the inductive step and the proof.

Optimal Substructure

This proof implicitly relies on a concept called optimal substructure. This principle states that a shortest path between two nodes contains other shortest paths within it. For example, if s -> ... -> u -> v is a shortest path from s to v, then the subpath s -> ... -> u must be a shortest path from s to u. If it weren't, you could substitute a shorter path to u and create an even shorter path to v, a contradiction.

This property is a hallmark of problems that can be solved with greedy algorithms (like BFS for unweighted shortest paths, and Dijkstra's algorithm which we'll see later) and dynamic programming.

Conclusion

Today, we transitioned from the implementation of BFS to a formal, rigorous proof of its most important property. You have seen how the level-by-level nature of the algorithm, enforced by the FIFO queue, guarantees that it discovers vertices in increasing order of their true shortest path distance.

Key Takeaways:

• The "shortest path" in an unweighted graph is the path with the fewest edges.
• The proof of correctness for BFS relies on two main ideas:
  1. Queue Monotonicity: Vertices in the queue are always sorted by non-decreasing distance from the source.
  2. Proof by Induction: By assuming correctness for all paths of length up to k, we can prove correctness for paths of length k+1, using a proof by contradiction to show that no shorter path could possibly be found.
• This property demonstrates the optimal substructure inherent in shortest path problems.

With both DFS and BFS now thoroughly covered, you have the foundational traversal algorithms needed for a vast range of graph problems. In our next lesson, we will apply DFS to solve a common problem: finding all connected components in an undirected graph.