Shortest Path — Unweighted Graphs (BFS)

One of the most elegant results in graph theory is that Breadth-First Search (BFS) naturally computes shortest paths in unweighted graphs. This isn't a coincidence or a fortunate side effect—it's a fundamental property that emerges directly from how BFS explores nodes in expanding concentric "rings" from the source.

When every edge has the same cost (or no cost at all), the problem of finding the shortest path transforms into finding the path with the fewest edges. BFS, by its very design, visits nodes in order of increasing distance from the source. The first time BFS reaches any node, it has found the shortest path to that node. This guarantee—first visit equals optimal visit—is what makes BFS the definitive algorithm for unweighted shortest paths.

Before we dive into BFS, let's rigorously define the problem we're solving.

Definition: Given a graph G = (V, E) and two vertices s (source) and t (target), the shortest path from s to t is a sequence of edges connecting s to t such that some metric is minimized.

In weighted graphs, this metric is typically the sum of edge weights. In unweighted graphs, all edges are considered equal, so the metric becomes the number of edges (or equivalently, the number of hops) in the path.

This distinction is crucial:

Why the distinction matters:

The simplification in unweighted graphs—all edges having equal "cost"—unlocks a dramatically more efficient algorithm. While Dijkstra's algorithm requires a priority queue and O((V+E) log V) time, BFS achieves the same result with a simple FIFO queue in O(V + E) time. This isn't just a constant factor improvement; it's an algorithmic class difference.

The unweighted shortest path problem asks: What is the minimum number of edges I must traverse to get from s to t? This is equivalent to asking: What is the fewest number of steps, hops, or transitions required?

To understand why BFS finds shortest paths, we must deeply understand how BFS explores a graph. BFS uses a FIFO (First-In, First-Out) queue to manage the frontier of exploration. This queue discipline has a profound consequence: nodes are visited in order of their distance from the source.

The Level-Order Property:

When BFS starts from source vertex s:

• First, it processes s (distance 0)
• Then, it processes all neighbors of s (distance 1)
• Then, it processes all neighbors-of-neighbors that weren't already visited (distance 2)
• And so on...

This creates "levels" or "layers" emanating outward from s, like ripples in a pond. All nodes at distance k are processed before any node at distance k+1.

Why does the FIFO queue guarantee level-order?

Consider the queue's behavior:

1. We start by enqueueing s. Queue: [s]
2. We dequeue s and enqueue all its neighbors. Queue: [A, B, C]
3. We dequeue A (first of distance-1 nodes), enqueue A's unvisited neighbors. Queue: [B, C, D]
4. We dequeue B (still distance-1), enqueue B's unvisited neighbors. Queue: [C, D, E]
5. We dequeue C (last distance-1 node), enqueue C's unvisited neighbors. Queue: [D, E, F]
6. Now we dequeue D (first distance-2 node)...

Notice: We fully exhaust all distance-1 nodes before touching any distance-2 nodes. This is because we added all distance-2 nodes after all distance-1 nodes, and FIFO preserves this ordering.

Key Insight: The FIFO discipline ensures that when we add a node's neighbors, those neighbors are placed at the back of the queue, behind all currently queued nodes. Since currently queued nodes are at the same or earlier level, the level-order is maintained.

We now state and prove the fundamental theorem that justifies using BFS for shortest paths.

Theorem (BFS Shortest Path Optimality):

Let G = (V, E) be an unweighted graph, and let s ∈ V be a source vertex. For any vertex v reachable from s, the BFS algorithm starting from s visits v at minimum distance d(s, v), where d(s, v) is the length of the shortest path from s to v.

Proof Sketch:

We prove this by strong induction on the distance from s.

Base Case (d = 0): The only vertex at distance 0 from s is s itself. BFS starts by visiting s at distance 0. ✓

Inductive Hypothesis: Assume that for all vertices u with d(s, u) ≤ k, BFS visits u at the correct minimum distance.

Inductive Step: Consider any vertex v with d(s, v) = k + 1.

• Since d(s, v) = k + 1, there exists a shortest path from s to v of length k + 1.
• Let u be the vertex immediately before v on this shortest path. Then d(s, u) = k.
• By the inductive hypothesis, BFS visits u at distance k.
• When BFS processes u, it examines all neighbors of u, including v.
• If v hasn't been visited yet, BFS assigns v distance k + 1 (exactly d(s, v)).
• If v was already visited, it must have been assigned distance ≤ k + 1. But since d(s, v) = k + 1 is the minimum, v's assigned distance cannot be less than k + 1. Thus v was assigned exactly k + 1. ✓

Corollary: First Visit is Optimal Visit

An important consequence of this theorem: the first time BFS discovers a vertex v is when it finds the shortest path to v. Any subsequent encounter with v (through a different edge from a different node) would be from a vertex at equal or greater distance from s—and since v is already marked visited, BFS ignores this redundant discovery.

This property is what gives BFS its elegance. We don't need to compare path lengths, maintain "tentative distances" that might be improved later, or use any priority queue. The queue's FIFO nature, combined with the visited set, automatically ensures optimality.

Understanding why BFS is the right choice requires comparing it to alternatives. Each comparison illuminates a different aspect of BFS's suitability for unweighted shortest paths.

Why Not Use Dijkstra's Algorithm for Unweighted Graphs?

Dijkstra's algorithm works on unweighted graphs—if you treat each edge as having weight 1. But it's overkill:

Using Dijkstra's for unweighted graphs is like using a sledgehammer to hang a picture frame. It works, but there's a better tool.

Why Not Just Try All Paths?

A naive brute-force approach might enumerate all possible paths and select the shortest. This is catastrophically slow:

• An unweighted graph with V vertices could have O(V!) simple paths
• Even with cycle detection, the number of paths can be exponential
• BFS explores each vertex and edge exactly once: O(V + E)

BFS achieves shortest paths not by comparing all possibilities, but by clever ordering of exploration that makes comparison unnecessary.

Beyond the formal proof, let's develop deep intuition for why BFS finds shortest paths.

The Expanding Frontier Metaphor:

Imagine dropping a stone into a still pond at the source vertex. Ripples expand outward in concentric circles. Each "ring" represents nodes at the same distance from where the stone landed.

• Ring 0: The source vertex itself
• Ring 1: All vertices directly connected to the source
• Ring 2: All vertices connected to Ring 1 that aren't in earlier rings
• And so on...

BFS simulates this expansion. The queue contains the current frontier—all nodes in the current ring being processed. As we process each frontier node, we discover nodes for the next ring and add them to the queue.

Why does this guarantee shortest paths?

To reach a node in Ring k, you must pass through a node in Ring k-1. There's no shortcut that "jumps" rings because:

1. If a direct edge existed from Ring k-2 to Ring k, that node would actually be in Ring k-1 by definition
2. The ring number IS the distance—defined as the minimum edges from the source

So when BFS reaches a node for the first time, it's necessarily through a node in the previous ring—giving us exactly the minimum distance.

The "Why Not Earlier?" Argument:

Another way to see optimality: Suppose BFS reports distance d to node v. Could v's true distance be less than d?

No, because:

1. Every node with distance d-1 was processed before v was discovered
2. If v had a shorter path, v would have been discovered when processing a closer node
3. But v was discovered at step d, meaning no closer node connects to v
4. Therefore, d is the true minimum distance

This is a proof by contradiction hidden in the BFS mechanics. The queue order makes "what if there's a shorter path?" impossible.

The BFS shortest path technique appears across diverse problem domains. Understanding these applications deepens your pattern recognition for when to apply this technique.

Implicit Graphs:

A powerful insight is that the graph doesn't need to exist explicitly in memory. Many shortest path problems involve implicit graphs—where vertices and edges are derived on-the-fly from a state space.

Example: Knight's Minimum Moves

To find the minimum moves for a chess knight to reach from (0, 0) to (x, y):

• Vertices: All valid chessboard positions
• Edges: Valid knight moves (L-shaped: 2 squares in one direction, 1 in perpendicular)
• Graph is implicit: we compute neighbors when needed, not stored beforehand

BFS explores this implicit graph, computing shortest paths without ever materializing the full graph structure.

Knowing when BFS is the right tool is as important as knowing how to use it. Here are the key indicators that a problem requires BFS shortest paths:

Mental Transformation Exercise:

When you encounter a problem, practice transforming it into graph terms:

1. What are the vertices? (States, positions, configurations)
2. What are the edges? (Transitions, moves, operations)
3. Are all edges equal cost? (If yes, BFS. If no, Dijkstra or Bellman-Ford)
4. What constitutes the "shortest path"? (Minimum hops = BFS)

This transformation is the key skill. Once you see the problem as an unweighted graph shortest path, the solution is mechanical—just run BFS.

Let's crystallize the key insights from this page:

What's Next:

Knowing that BFS finds shortest distances is only half the story. In practice, we usually need to reconstruct the actual path, not just know its length. The next page explores parent tracking—the technique of recording which vertex led to each discovered vertex, enabling us to trace back from destination to source and recover the full shortest path.