BFS pathfinding

O(V + E)

On an unweighted grid, breadth-first search finds the shortest path between two cells. It expands outward from the start in waves: all cells one step away, then two steps, and so on, using a queue. Because every move costs the same, the first time the wave touches the goal it has reached it by a shortest route, which you recover by following parent pointers back. BFS is complete and optimal here, but it explores blindly in all directions — it has no sense of where the goal is — so it can visit far more cells than a guided search. It runs in O(V + E).

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Put the start cell in a queue and mark it seen.
  2. Dequeue the nearest cell and expand it.
  3. Add each free, unseen neighbour to the queue, remembering where it came from.
  4. When the goal is dequeued, follow the parent pointers back to trace the shortest path.

Pseudocode

1bfsPath(grid, start, goal):          # O(V + E)2  queue ← [start]; seen ← {start}3  while queue not empty:4    cell ← queue.dequeue()           # nearest first5    if cell = goal: stop6    for nbr in free neighbours(cell):7      if nbr not seen:8        prev[nbr] ← cell; seen.add(nbr)9        queue.enqueue(nbr)10  walk prev from goal back to start  # shortest path