AdvancedGraphs
Shortest path in a grid is BFS
In an unweighted grid or graph, BFS reaches every cell by the fewest steps first. Mark cells visited when you enqueue them.
The idea
BFS explores in waves: everything 1 step away, then 2, then 3. So the first time it reaches a cell, that's the shortest way there.
Mark a cell visited when you put it in the queue, not when you take it out, or the same cell gets queued many times.
Worked example
Rotting Oranges: every minute, rot spreads to neighbours
- Queue every rotten orange at minute 0 (multi-source BFS).
- Each round of the queue is one minute: rot the fresh neighbours and queue them.
- When the queue empties, any fresh orange left means −1; otherwise the minutes taken.
In code (Python)
from collections import deque
def shortest_path(grid, start, goal):
rows, cols = len(grid), len(grid[0])
queue = deque([(start, 0)])
seen = {start}
while queue:
(r, c), dist = queue.popleft()
if (r, c) == goal:
return dist
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in seen:
seen.add((nr, nc)) # mark on enqueue
queue.append(((nr, nc), dist + 1))
return -1O(rows × cols) time and space.
How to spot it
- “minimum steps / moves / minutes”, mazes, spreading over a grid, word ladders.
Common mistakes
- Using DFS for shortest paths (it finds a path, not the shortest).
- Marking visited on dequeue.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →