BFS: Shortest Path in a Grid, From Brute-Force DFS to Early-Exit BFS
One problem, three stages: make it work, make it fast, make it lean. Step through each stage in the visualizer, then run all three on a big input in the benchmark and watch the brute force overheat.
The real-world version
A warehouse robot has to reach a shelf on a floor plan where some aisles are blocked. It needs the fewest moves, and the floor plan can be hundreds of cells on each side.
The problem
Given a grid where . is open, # is a wall, S is the start and E is the exit, return the fewest moves (up, down, left, right) from S to E, or -1 if it can't be reached.
S.#... ..#.#. .....# .##... ...#.E → 9
Stage 1 · Smelt: Make it work
Depth-first search tries every simple path from S, backtracks, and keeps the shortest one that reached E. It's the natural first idea, and it does find the right answer.
def shortest(grid, start, end):
best = float('inf')
seen = {start}
def dfs(cell, steps):
nonlocal best
if cell == end:
best = min(best, steps)
return
for nxt in neighbours(grid, cell):
if nxt not in seen:
seen.add(nxt)
dfs(nxt, steps + 1)
seen.remove(nxt) # backtrack
dfs(start, 0)
return best if best < float('inf') else -1Why it's not enough: The number of possible paths explodes: even an empty 20×20 grid has more paths than any computer can enumerate.
Stage 2 · Hammer: Make it fast
BFS explores in rings: every cell 1 move away, then 2, then 3. The first time it reaches a cell is via a shortest path, so each cell is visited once and never again.
from collections import deque
def shortest(grid, start, end):
q = deque([(start, 0)])
visited = {start}
best = -1
while q:
cell, d = q.popleft()
if cell == end:
best = d
for nxt in neighbours(grid, cell):
if nxt not in visited:
visited.add(nxt)
q.append((nxt, d + 1))
return bestWhy it's not enough: Correct and linear. It keeps a separate visited set, though, and keeps exploring after the answer is known.
Stage 3 · Polish: Make it lean
Same BFS, tightened: one distance table does the job of the visited set and the step counter, and we return the moment the exit is discovered, because BFS guarantees nothing found later can be shorter.
from collections import deque
def shortest(grid, start, end):
dist = {start: 0} # doubles as 'visited'
q = deque([start])
while q:
cell = q.popleft()
for nxt in neighbours(grid, cell):
if nxt not in dist:
dist[nxt] = dist[cell] + 1
if nxt == end:
return dist[nxt] # first discovery is shortest
q.append(nxt)
return 0 if start == end else -1Why it holds up: Optimal for unweighted grids. On a big floor plan with a nearby exit, the early exit skips most of the grid.
X-ray: watch it run
Benchmark: will the forge overheat?
Run all three stages on a large input in your browser and compare the work each one does.
In the interview
If the edges have different costs (traffic, slopes), BFS no longer gives the shortest path. Say so, and name Dijkstra as the next step. It's the follow-up question interviewers almost always ask.
Go deeper: BFS — Breadth-First Search