What you're seeing
The grid is a graph: each open cell is a node, joined to its four neighbors. BFS starts at the source and explores in layers — first all cells one step away, then all cells two steps away, and so on — so the blue frontier spreads outward like a flood (a diamond, because diagonal moves aren't allowed). The instant the wave reaches the target, we stop and walk the parent pointers backward to trace the path that got there. Because the wave reaches every cell as early as possible, that path is a shortest one.
The rule
bfs(source):
queue = [source]; dist[source] = 0
while queue not empty:
u = queue.dequeue() # FIFO ⇒ nearest-first
for each neighbor v of u, not yet seen:
dist[v] = dist[u] + 1
parent[v] = u
queue.enqueue(v)
The FIFO queue is the whole trick: it hands back cells in nondecreasing distance order, so the search never jumps ahead to a farther cell before finishing a nearer one.
The invariant
The queue always holds cells of at most two adjacent distances, in order, and: when a cell is first dequeued (first reached), its recorded dist is its true shortest-path distance from the source. Induction on distance: suppose every cell at distance ≤ d was discovered with the correct value. A cell at distance d+1 has some neighbor at distance d; that neighbor is dequeued before any cell of distance d+1 (FIFO order), and discovers it with dist = d+1 — which is correct, since it cannot be closer. So no cell is ever assigned too large a distance, and the parent links form a shortest-path tree. This is exactly why BFS solves shortest paths on unweighted graphs (and why it fails once edges have weights — that's Dijkstra's job).
The cost
Every cell is enqueued and dequeued once, and each edge is examined once from each side — linear in the size of the graph. On a grid of V cells with 4-connectivity, E ≈ 2V, so it's O(V). The space is the queue plus the distance/parent arrays. Raise the wall density and watch the wave detour around obstacles — but it still finds the genuinely shortest route through the maze, never just the first route.
In the wild
BFS is the backbone of unweighted shortest paths and reachability: grid pathfinding in games and robotics (often as the base case under A*), the "degrees of separation" / friend-suggestion queries in social graphs, web crawling level by level, finding connected components and testing bipartiteness, garbage-collection mark phases, and network-broadcast / flood-fill (the paint-bucket tool). Whenever the question is "what's reachable, and how few hops away," BFS is the answer — and its layered structure makes it the natural starting point for the weighted and heuristic search algorithms that build on it.
Try this
Step through with ▶| and watch the distance readout tick up one per layer — each blue ring is exactly one step farther than the last. Crank Wall density up: the wave splits and curls around walls, and the green path bends with it, yet it's always a shortest path through whatever maze remains.
References
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §20.2 (Breadth-first search) — the algorithm, the shortest-path proof, and the BFS tree. MIT Press, 2022.
- Moore, E. F. "The shortest path through a maze." Proc. Int. Symp. on the Theory of Switching, 1959 — an origin of BFS.
- Sedgewick & Wayne. Algorithms, 4th ed., §4.1 (Undirected Graphs). algs4.cs.princeton.edu/41graph.