Why BFS Works for This

Throughout this module, we've asserted that BFS finds shortest paths in unweighted graphs. We've shown how it works, but truly understanding why requires looking beneath the surface at the fundamental properties that make this guaranteed.

This isn't mere academic curiosity. Understanding the why is essential for:

• Knowing when you CAN use BFS (unweighted or unit-weight edges)
• Knowing when you CANNOT use BFS (weighted edges with different costs)
• Adapting BFS to novel problems (recognizing the invariants that must hold)
• Debugging when things go wrong (identifying which property was violated)

The entire correctness of BFS for shortest paths rests on a single elegant insight:

In a FIFO queue, if all items of level k are added before any item of level k+1, then all items of level k will be processed before any item of level k+1.

This sounds almost trivially true, but its implications are profound. Let's trace through exactly why this matters for shortest paths.

How BFS Maintains Level Order:

1. We start with the source at level 0 in the queue: [s]
2. We process s and add all its neighbors (level 1 vertices) to the queue
   • Queue after: [a, b, c] (all level 1)
3. We process a (first level 1 vertex) and add its new neighbors (level 2)
   • Queue after: [b, c, d, e] (level 1, level 1, level 2, level 2)
4. We process b (second level 1 vertex) and add its new neighbors
   • Queue continues to maintain order...

Critical observation: When we process a level-k vertex, we add level-(k+1) vertices to the back of the queue. All remaining level-k vertices are still ahead in the queue. Therefore, level-(k+1) vertices are processed only after ALL level-k vertices.

Formal Statement (Level-Order Lemma):

During BFS from source s, let d(v) denote the length of the shortest path from s to v. The queue at any point contains vertices at most two consecutive distance levels: all vertices with distance k, followed by some vertices with distance k+1, for some k ≥ 0.

This lemma captures the queue's structure: it's always "stratified" by distance. We never have a jumbled mix of near and far vertices.

Let's prove rigorously that BFS computes correct shortest path distances.

Theorem: For any vertex v reachable from source s in an unweighted graph, BFS assigns distance[v] = d(s, v), where d(s, v) is the true shortest path length from s to v.

Proof by Strong Induction:

Base Case (k = 0):

• The only vertex at distance 0 from s is s itself.
• BFS initializes distance[s] = 0. ✓

Inductive Hypothesis:

• Assume that for all vertices u with d(s, u) ≤ k, BFS correctly assigns distance[u] = d(s, u).

Inductive Step (proving for k+1):

• Let v be any vertex with d(s, v) = k+1.
• By definition of shortest path, there exists a path s → ... → u → v where d(s, u) = k.
• By the inductive hypothesis, BFS correctly assigns distance[u] = k.
• When BFS processes u, it examines all neighbors of u, including v.
• Case 1: v has not been visited yet.
  • BFS assigns distance[v] = distance[u] + 1 = k + 1. ✓
• Case 2: v has already been visited (distance[v] already set).
  • v was discovered from some vertex w with distance[w] = distance[v] - 1.
  • By Level-Order Lemma, w was processed before or at the same time as u.
  • Therefore, distance[w] ≤ k, so distance[v] ≤ k + 1.
  • But d(s, v) = k + 1 is the minimum, so distance[v] ≥ k + 1.
  • Therefore, distance[v] = k + 1. ✓

Conclusion: By induction, BFS correctly computes shortest path distances for all reachable vertices. ∎

Understanding why BFS fails for weighted graphs illuminates what makes it work for unweighted graphs.

The Problem:

In a weighted graph, edges have different costs. A path through more edges might have lower total cost than a path through fewer edges.

Example:

What BFS Would Do:

1. Start at S, distance = 0
2. Process S, discover A (1 hop) and B (1 hop)
3. Queue: [A, B], both at "distance 1"
4. Process A first (or B, depending on order)
5. BFS thinks: shortest path to A is S→A with 1 hop

The Truth:

• Path S→A: 1 hop, but cost = 10
• Path S→B→C→A: 3 hops, but cost = 1+1+1 = 3

The 3-hop path is cheaper! BFS found the path with fewer edges, but not the path with lower cost.

Why the Proof Breaks:

Our proof relied on the fact that discovering a vertex v from a closer vertex u means v's distance is exactly d(u) + 1. In weighted graphs, "closer in hops" doesn't mean "closer in cost." The Level-Order Lemma still holds (for hop count), but hop count ≠ path cost.

BFS works whenever all edges have the same weight (not necessarily 1, just equal). This is called the "unit weight" or "uniform weight" condition.

Why Equal Weights Suffice:

If all edges have weight w (for any positive w), then:

• Total cost of a k-edge path = k × w
• Minimizing k automatically minimizes total cost
• BFS minimizes k, so it minimizes total cost

Example:

If all edges cost 7, a 3-edge path costs 21, and a 5-edge path costs 35. The fewer-hop path is always cheaper.

General Principle:

When all actions have equal cost, the fewest-action solution IS the minimum-cost solution.

This is why BFS works for:

• Mazes (each step costs 1)
• Word ladders (each transformation costs 1)
• Social network distance (each friendship is 1 hop)
• Puzzle solving (each move counts equally)

The "-1 BFS" Variant:

For graphs with edge weights 0 or 1 only, a modified BFS called "0-1 BFS" works in O(V + E):

• Use a deque (double-ended queue) instead of regular queue
• When following a 0-weight edge: add to front (these vertices are same distance)
• When following a 1-weight edge: add to back (these are 1 further)

This maintains the level-order invariant even with mixed 0/1 weights.

Understanding BFS for unweighted graphs helps understand Dijkstra's algorithm for weighted graphs.

The Key Difference:

Why Dijkstra's Needs a Priority Queue:

In weighted graphs, a vertex discovered later might have a shorter total distance. We can't rely on discovery order. Instead, we always process the vertex with the smallest tentative distance—guaranteed by a priority queue.

BFS as a Special Case:

BFS is actually Dijkstra's algorithm where all edges have weight 1:

• Priority queue degrades to FIFO queue (all same-level vertices have same priority)
• No relaxation needed (hop count discovery order = distance order)
• O((V + E) log V) simplifies to O(V + E) (no heap operations needed)

Conceptual Insight:

BFS works because with unit weights, the FIFO queue automatically maintains priority order. Vertices with distance k all have the same priority (k), and they're all added before vertices with distance k+1. The FIFO queue is a "free" priority queue when priorities come in ascending order.

When weights vary, priorities are no longer in order, and we need an explicit priority queue to process vertices in correct order.

Let's enumerate the key invariants that hold throughout BFS execution. These invariants are the "contracts" that guarantee correctness.

Verifying Invariants:

Initialization: Before the main loop, only the source is visited with distance 0. All invariants hold trivially.

Maintenance: Each iteration:

1. Dequeues a vertex at the current minimum level (Invariant 2)
2. Visits neighbors not yet visited, assigning distance = current + 1 (Invariants 1, 4, 5)
3. Adds new vertices to back of queue (Invariant 2 preserved)
4. Marks new vertices visited (Invariant 3)

Termination: When the queue empties, all reachable vertices have been assigned correct distances.

Let's address common misunderstandings about BFS and shortest paths.

Detailed Misconception: "Mark Visited When Processing"

This is a subtle but important error:

Incorrect:

while queue:
    current = queue.popleft()
    visited.add(current)  # WRONG: too late!
    for neighbor in graph[current]:
        if neighbor not in visited:
            queue.append(neighbor)

Problem: A vertex might be added to the queue multiple times before being processed, wasting time and potentially causing issues.

Correct:

while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
        if neighbor not in visited:
            visited.add(neighbor)  # RIGHT: mark immediately
            queue.append(neighbor)

Key Insight: Mark visited at discovery time (when adding to queue), not processing time (when dequeuing). This ensures each vertex is added exactly once.