Bidirectional BFS
01 / The one-sentence essence
Run BFS from both endpoints simultaneously. As soon as the two frontiers touch, the shortest path is found. The win is exponential in the depth:O(b^d)becomesO(b^(d/2))— useful whenever both the source and the target are known.
Problemshortest path length — source to target on an unweighted graphInputgraph=mesh, A → F
BFS simultaneously from A (forward) and F (backward). Initialize distS[A] = 0, distT[F] = 0, frontiers = single seed each.
step
0 / 19
fronts |S|, |T|
1, 1
visited
1 + 1
path length
—
0 / 19
02 / The pattern signature
# layer-by-layer bidirectional BFSdistS ← { s: 0 }; distT ← { t: 0 }frontS ← {s}; frontT ← {t}while frontS and frontT:if |frontS| ≤ |frontT|: expand frontS against distTelse: expand frontT against distSfor u in front for v in adj[u]:if v in other.dist: return same[u] + other[v] + 1if v not in same.dist: same[v] = same[u] + 1; nextFront ← vreturn −1 # disconnected
03 / When to recognize this pattern
"shortest transformation / mutation"
Word ladders, gene mutations, dial locks — any state-space search where the start and end are concrete states, and edges are uniform-cost (one hop = one transformation).
"both endpoints known"
The technique only helps when you have a concrete target. For one-to-many shortest-path (Dijkstra, BFS-from-source), plain one-sided BFS is simpler and asymptotically the same.
"branching factor seems too big for BFS"
Word-ladder with 26 letters × L positions, or a 4-wheel combination lock with 10 digits each — the branching factor
b looks intimidating. Bidirectional BFS halves the depth so b^(d/2) becomes manageable."shortest path on an unweighted graph"
BFS finds shortest in unweighted; bidirectional only adds value. For weighted graphs, reach for bidirectional Dijkstra (advanced and rarely interview-relevant).
04 / Common pitfalls
Expanding the larger frontier first.
The whole point is to keep both frontiers balanced — always expand the smaller one. If you consistently expand whichever you reached first, one side blows up and the speedup is lost.
Checking the other side after updating, not before.
The "meet" test happens on every neighbor probe — before you add it to your own visited set, check the opposite side's set. Otherwise you might miss the first meeting and report a longer path than the true shortest.
Reversing the answer formula.
On meet through edge
u → v (with u from the current side, v already visited by the other), the answer is distSide[u] + distOther[v] + 1 — the +1 for the bridging edge itself. Off-by-one is the canonical bug.Returning the first meet instead of the shortest one.
When you expand a layer, multiple meeting candidates can appear in the same round — process the whole layer before committing to an answer if path-reconstruction matters (otherwise the first meet found at that depth is shortest by BFS invariant).
05 / Go practice — on LeetCode
medium10
01Minimum Genetic Mutation— LC 433→0201 Matrix— LC 542→03Open the Lock— LC 752→04Rotting Oranges— LC 994→05Shortest Path in Binary Matrix— LC 1091→06As Far from Land as Possible— LC 1162→07Jump Game III— LC 1306→08Get Watched Videos by Your Friends— LC 1311→09Minimum Jumps to Reach Home— LC 1654→10Shortest Path to Get Food— LC 1730→
hard9
01Word Ladder II— LC 126→02Word Ladder— LC 127→03Cut Off Trees for Golf Event— LC 675→04Sliding Puzzle— LC 773→05Bus Routes— LC 815→06K-Similar Strings— LC 854→07Shortest Path to Get All Keys— LC 864→08Minimum Number of Flips to Convert Binary Matrix to Zero Matrix— LC 1284→09Shortest Path in a Grid with Obstacles Elimination— LC 1293→