BFS shortest path (unweighted)

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Change the word "hit" into "cog" one letter at a time, where every intermediate word must be in a dictionary: {hot, dot, dog, lot, log, cog}. What is the fewest steps? By hand you might try: hit → hot → dot → dog → cog, five words, four changes. Is there anything shorter? You cannot be sure unless you have tried every shorter possibility. Depth-first exploration can wander: hit → hot → lot → log → cog is also a ladder, and a depth-first search that happened to go down the lot branch first would report it, which is the same length here but in general could be longer than the best.

What you want is to try all one-step words, then all two-step words, and so on, so that the first time you see "cog" you know nothing shorter exists.

Build the structure, one piece at a time

Piece one: the graph. Words are nodes; two words are joined if they differ in exactly one letter. We never build it explicitly: to find a word's neighbours, change each position to each of 26 letters and keep those that are in the dictionary.

Piece two: a queue holding (word, steps so far), and a visited set so that a word is explored only once. Mark a word visited the moment it is pushed, not when it is popped, or the same word can enter the queue many times.

Piece three: the loop. Pop the front. If it is the target, its steps count is the answer. Otherwise push every unvisited neighbour with steps + 1.

Every word at length 3 was handled before any at length 4. That is the layering the by-hand method wanted.

Why it is correct

The invariant: the queue holds nodes in non-decreasing distance, and the distances present differ by at most one. Initially it holds one node at distance 0. Popping a node at distance d pushes nodes at d + 1 to the back, behind everything at d and d + 1 already there, so the order is preserved.

the first time a node is pushed, its recorded distance = the length of a shortest path to it

Suppose some node v were first reached with a distance larger than its true shortest distance k. Then along a true shortest path there is a node u at distance k − 1 that was popped before anything at distance k or more was popped, and popping u would have pushed v at distance k. Contradiction. So the recorded distance is exact, and in particular the first time the target is seen is optimal.

Why it is fast

Each node is pushed and popped at most once, and each edge is examined at most twice, so O(V + E). For Word Ladder with N words of length L, generating neighbours costs 26 × L per word, so O(N × 26 × L) overall. Depth-first search has the same cost but no guarantee of shortness; trying all ladders by hand is exponential.

How to recognise it in an interview

"Minimum number of steps", "shortest path" or "fewest moves" where every step costs the same: a grid with unit moves, a word ladder, a lock dial, a snakes-and-ladders board, a knight on a chessboard. Say: "All edges have equal weight, so BFS from the source finds shortest distances; the first time I reach the target I stop." Word Ladder is this exactly. Shortest Path in Binary Matrix runs it on cells with 8 neighbours. Bus Routes builds the graph with routes as nodes, joined when they share a stop, and BFS counts buses instead of stops.

02The idea in one line

Layer by layer from the source; distance = number of layers.

Reach for it when: Shortest path in binary matrix, word ladder, open the lock, snakes and ladders, bus routes.

Cost: O(V + E) time.

03The walk-through, step by step

The video works one example: Word Ladder hit → cog. These are its captions in order, so you can follow without the video or check a step you missed.

1. Unweighted edges: the first time BFS reaches a node, that is its shortest distance
2. Start at hit with length 1; the first time cog is reached is the shortest
3. Pop hit (1): discover hot at 2
4. Pop hot (2): discover dot, lot at 3
5. Pop dot (3): discover dog at 4
6. Pop lot (3): discover log at 4
7. Pop dog (4): discover cog at 5
8. cog reached at length 5: hit→hot→dot→dog→cog
9. DFS could find a longer ladder first; BFS explores by layers, so the first hit is optimal
10. Every word dequeued once, in distance order: O(V + E)

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).