BFS Shortest Paths on Unweighted Graphs

Given an unweighted, directed or undirected graph `G = (V, E)` and a source vertex `s`, the single-source shortest path problem asks for `δ(s, v)`, the minimum number of edges on any path from `s` to `v`, for every vertex `v`. When no path exists, `δ(s, v) = ∞`. Breadth-first search solves this exactly: starting from `s`, it visits all vertices at distance 1, then all vertices at distance 2, and so on, layer by layer. This layered exploration order is what makes BFS a shortest-path algorithm and not merely a graph traversal. The mechanism that enforces this layering is a FIFO queue. Every vertex, when first discovered, is pushed onto the back of the queue and given a distance label equal to (distance of its discoverer) + 1. Because the queue is FIFO, vertices are processed in exactly the order they were discovered — and it is this ordering discipline, not any explicit notion of "distance," that forces BFS to finish an entire layer before starting the next one. We formalize this as the queue-monotonicity invariant: at any moment during execution, if the queue holds vertices `v₁, v₂, …, vₖ` from front to back, then ``` d[v1] ≤ d[v2] ≤ ... ≤ d[vk] ≤ d[v1] + 1 ``` In words: distances in the queue are sorted and span at most two consecutive integers. This one structural fact is the entire engine behind BFS's correctness proof, and it is worth internalizing before looking at any pseudocode. Alongside distance labels, BFS typically also records a predecessor pointer `π[v]`, the vertex from which `v` was first discovered. The predecessor pointers form a BFS tree, a spanning tree (of the reachable component) in which the tree-path from `s` to any `v` is a shortest path in the original graph. This tree is what lets you reconstruct a shortest path, not just know its length.

BFS maintains three pieces of per-vertex state: a color (`WHITE` = undiscovered, `GRAY` = discovered but not fully processed, `BLACK` = finished), a distance `d[v]`, and a predecessor `π[v]`. The source is discovered first with distance 0, and every other vertex's distance is derived by adding 1 each time it is reached via an edge from a currently-processing vertex. ``` BFS(G, s): for each vertex u in V(G): color[u] = WHITE d[u] = INFINITY π[u] = NIL color[s] = GRAY d[s] = 0 π[s] = NIL Q = empty queue ENQUEUE(Q, s) while Q is not empty: u = DEQUEUE(Q) for each v in Adj(u): if color[v] == WHITE: color[v] = GRAY d[v] = d[u] + 1 π[v] = u ENQUEUE(Q, v) color[u] = BLACK return d, π ``` Reconstructing a shortest path from `s` to a target `t` is a walk backward through predecessors: ``` PRINT-PATH(π, s, t): if t == s: print s else if π[t] == NIL: print "no path exists" else: PRINT-PATH(π, s, π[t]) print t ``` Two design choices deserve emphasis. First, a vertex is marked `GRAY` (and given its final `d` value) the moment it is discovered, not when it is dequeued — this ensures no vertex is enqueued twice, which is what keeps the running time linear. Second, the check `color[v] == WHITE` is the only gate for enqueuing; once a vertex is colored, its distance is frozen forever. The proof below shows why freezing on first discovery is always correct.

Time complexity. Every vertex is enqueued at most once (it turns from `WHITE` to `GRAY` immediately upon enqueuing, and the `WHITE` check prevents re-enqueuing), so the `while` loop body runs `O(V)` times. Inside, the algorithm scans `Adj(u)` for the dequeued `u`; summed over all vertices, this is `O(E)` for directed graphs and `O(2E) = O(E)` for undirected graphs (each edge appears in two adjacency lists). Initialization costs `O(V)`. Total running time: ``` O(V + E) ``` This is optimal in the sense that any correct algorithm must at least read the input, which already costs `Θ(V + E)` in the adjacency-list representation.

Space complexity. The color, distance, and predecessor arrays are each `O(V)`; the queue holds at most `V` vertices at once. Total space is `O(V)`, on top of the `O(V + E)` needed to store the graph itself.

Correctness — the queue-monotonicity invariant. Define `δ(s, v)` as the true minimum number of edges from `s` to `v` (∞ if unreachable). We want to prove that BFS's `d[v]` equals `δ(s, v)` for every vertex, and we do it via the following invariant, checked at the top of every iteration of the `while` loop (i.e., immediately before each `DEQUEUE`): > Invariant Q. If the queue currently contains vertices `v₁, v₂, …, vₖ` in front-to-back order, then > `d[v₁] ≤ d[v₂] ≤ ⋯ ≤ d[vₖ] ≤ d[v₁] + 1`, > and every vertex ever dequeued so far has `d` equal to its final, correct value. Base case. Just after `s` is enqueued, the queue contains only `s` with `d[s] = 0`. The chain of inequalities holds trivially (a single element). Inductive step. Suppose Invariant Q holds when the queue is `v₁, …, vₖ` (front to back). We dequeue `u = v₁`. By the invariant, `d[u] = d[v₁]` is the smallest distance value present, and every other queued vertex has distance `d[u]` or `d[u] + 1`. Process `Adj(u)`: for each white neighbor `w`, we set `d[w] = d[u] + 1` and append `w` to the back of the queue. Two things must be checked to re-establish Invariant Q for the new queue `v₂, …, vₖ, w₁, …, wₘ`: 1. The remaining old entries `v₂, …, vₖ` still satisfy `d[v₂] ≤ ⋯ ≤ d[vₖ] ≤ d[u] + 1` (this is inherited unchanged from before, since we only removed the front element). 2. Every newly appended `wⱼ` has `d[wⱼ] = d[u] + 1`, which is `≥ d[vₖ]` (since `d[vₖ] ≤ d[u] + 1` from point 1) — so appending them at the back preserves the non-decreasing order — and it is `≤ d[v₂] + 1` since `d[v₂] ≥ d[u]` implies `d[v₂] + 1 ≥ d[u] + 1 = d[wⱼ]`. Hence the new queue again satisfies the "sorted, span-at-most-one" property. This completes the induction, so Invariant Q holds throughout the entire execution.

Deriving `d[v] = δ(s, v)` from Invariant Q. We now prove, by strong induction on `δ(s, v)`, that whenever BFS assigns a finite `d[v]`, it equals `δ(s, v)`, and that BFS assigns a finite `d[v]` to every vertex reachable from `s`.

• `δ(s, s) = 0`, and BFS sets `d[s] = 0` directly. Correct.
• Suppose every vertex `v` with `δ(s, v) = k` is correctly discovered with `d[v] = k` (inductive hypothesis for all values `< k+1`). Let `w` be any vertex with `δ(s, w) = k + 1`. By definition of shortest-path distance, `w` has some neighbor `u` on a shortest path with `δ(s, u) = k`. By the inductive hypothesis `u` is discovered with `d[u] = k`, and since `u` is eventually dequeued (every discovered vertex is eventually dequeued, because the queue only shrinks by removing what it grows by, and the algorithm halts only when empty), BFS scans `Adj(u)` and reaches `w`. If `w` is still `WHITE` at that moment, it is assigned `d[w] = d[u] + 1 = k + 1`, matching `δ(s, w)`.
• We must rule out `w` being colored before this scan with a wrong (too-small or too-large) distance. Suppose for contradiction `w` were discovered earlier via some other vertex `x` with `d[w] = d[x] + 1 ≠ k+1`. Since `δ(s,w) = k+1` is the true minimum, no path of length `< k+1` reaches `w`, so `d[x] + 1` cannot be `< k+1`; thus if it is wrong, it must be `d[x] + 1 > k + 1`, i.e., `d[x] ≥ k + 1`. But Invariant Q says all vertices currently in the queue (which includes `x`, since `x` must be dequeued at or before the time `u` is dequeued for `w` to have already been discovered through `x`) have distances within 1 of the front, and `u` — with `d[u] = k` — is in or has passed through the front of the queue no later than `x`. This forces `d[x] ≤ d[u] + 1 = k+1`, and combined with `d[x] ≥ k+1` gives `d[x] = k+1`— but then `x` itself would need `δ(s,x) ≤ k` to have been dequeued at a point where the queue front distance is `≤ k`, which by the inductive hypothesis on smaller distances means `x` was assigned correctly, contradicting `δ(s,x) \ne k`. Careful bookkeeping of Invariant Q's "span at most 1" clause is precisely what blocks any vertex from ever being discovered too early — the queue simply cannot contain a vertex with distance `k` while simultaneously exposing a would-be distance-`(k+2)` discovery, since all frontier distances present differ by at most 1.

The clean takeaway, stated without the contradiction bookkeeping: because the queue never holds distances spanning more than two consecutive integers, vertices are discovered in non-decreasing order of true distance, so the first time any vertex is colored is necessarily via a shortest path. Since BFS freezes `d[v]` at first discovery and never revisits a colored vertex, `d[v] = δ(s, v)` for all reachable `v`, and unreachable vertices retain `d[v] = ∞` since they are never enqueued. This is the full correctness argument.

Correctness of the BFS tree. Because `π[w] = u` is only set at the moment `d[w] = d[u] + 1` is assigned, following `π` pointers from any `v` back to `s` traces a path whose length is exactly `d[v] = δ(s, v)` — hence a genuine shortest path, not merely a path of that length by coincidence.

Tradeoffs. BFS is optimal for unweighted graphs but gives no useful information when edges have weights (it would count edges, not weighted cost). It also requires `Θ(V)` memory even for sparse queries, and it computes distances to all reachable vertices rather than to a single target, which is wasted work if only one target is needed (though early termination when the target is dequeued is a common, safe optimization since distances are finalized on discovery, not dequeue).

Consider the following small directed graph, with `s = A`: ``` A → B, A → C B → D C → D, C → E D → F E → F ``` Trace of the queue and distance assignments:

Final distances: `d[A]=0, d[B]=1, d[C]=1, d[D]=2, d[E]=2, d[F]=3`. Check against the invariant: right after step 1, the queue is `[B, C]` with `d = [1, 1]` — non-decreasing, span 0. After step 2, `[C, D]` with `d = [1, 2]` — non-decreasing, span exactly 1, never more. After step 3, `[D, E]` with `d = [2, 2]`. This matches Invariant Q at every step, and no vertex's `d` value is ever revised after being set — exactly as the proof predicts. Predecessors: `π[B]=A, π[C]=A, π[D]=B` (since `B` was processed before `C`, `D` is first discovered from `B`, not `C`), `π[E]=C`, `π[F]=D` (since `D` is dequeued at step 4, before `E` is dequeued at step 5, so `F` is discovered from `D` first). Reconstructing the shortest path to `F`: `π[F]=D, π[D]=B, π[B]=A`, giving `A → B → D → F`, length 3 — matching `d[F] = 3` exactly, and note this is shorter than the alternative route `A → C → E → F`, which is also length 3 in this particular graph, illustrating that BFS finds a shortest path, not necessarily a unique one, but always of minimum length.

Breadth-first search traces back to work on maze-solving and network routing in the mid-20th century, later formalized as a general graph-traversal paradigm and analyzed rigorously for shortest-path correctness in the algorithms literature of the 1970s–80s.

Unweighted shortest paths via BFS underlie systems where every "hop" has equal cost. Social networks use BFS to compute degrees of separation and mutual-connection suggestions. Web crawlers use BFS-order traversal to explore pages level by level, which naturally prioritizes pages closer (in link-distance) to seed URLs. Peer-to-peer and overlay networks use BFS-like flooding to determine hop-count distances between nodes. Puzzle solvers — the 15-puzzle, Rubik's Cube "God's number" searches on small state spaces, maze games — use BFS because each legal move counts as one unit-cost edge in the state graph. Network topology tools compute shortest routing paths in hop count using BFS before layering on weighted metrics. It is also the base case that motivates the broader Single-Source Shortest Paths Framework: replacing the FIFO queue with a priority queue ordered by tentative distance yields Dijkstra's algorithm, and BFS's discovery-order argument becomes the seed for the greedy-relaxation correctness proofs used there. Understanding BFS's invariant deeply is what makes the leap to weighted shortest paths, and eventually to Dijkstra's Algorithm and Bellman-Ford Algorithm, much more natural.

:::quiz[If BFS discovers vertex w via vertex u with d[u] = k, what distance is assigned to w?]

• d[w] = k, same as u
• d[w] = k - 1
• d[w] = k + 1 ✓
• d[w] is left as infinity until dequeued

Ask the tutor: How does the queue-monotonicity argument change when we move from BFS to Dijkstra's algorithm with a priority queue instead of a FIFO queue?