Breadth-first search
What is the shortest route when every step costs the same?
Explores the grid in rings around the start, nearest first. It finds the path with the fewest steps.
Breadth-first search keeps a queue of cells waiting to be explored. It takes the oldest one, adds its unvisited neighbours at the back and repeats. Because the queue is first in, first out, every cell at distance one is handled before any at distance two, and so on outward.
The first time it reaches the goal, no shorter route can exist. That guarantee holds only when all steps cost the same: with different costs it can return the route with the fewest steps but a higher total.
It knows nothing about where the goal is, so it spreads in every direction and examines a lot of cells.
Loading the demo…
The grid with breadth-first search selected. Draw walls and watch the search spread out as a ring.
- 01Put the start in a queue and mark it visited.
- 02Take the cell at the front of the queue.
- 03If it is the goal, follow the stored parents back to the start.
- 04Otherwise add each unvisited neighbour to the back of the queue, recording the cell it came from.
- 05Repeat until the queue is empty, which means there is no path.
function bfs(start, goal):
queue = [start]
parent = {start: none}
while queue is not empty:
cell = queue.pop_front()
if cell == goal: return path_from(parent, goal)
for n in neighbours(cell):
if n not in parent:
parent[n] = cell
queue.push_back(n)
return no_pathV is the number of cells and E the connections between them; on a grid both are proportional to the number of cells.
- Fewest steps, guaranteed.
- Complete: it finds a path whenever one exists.
- A dozen lines.
- Ignores costs: fewest steps is not always cheapest.
- Ignores where the goal is, so it fills a whole disc around the start.
- The frontier can get large.
- 01PathfindingOne of five searches you can run on walls you draw; here the frontier is a plain queue.