Given a grid map, how does a robot find the shortest way around the walls?
Key idea
Breadth-first search (BFS) spreads out from the start one ring at a time, like ripples in a pond. The first time it reaches the goal, it has found a path with the fewest moves. Dijkstra's algorithm does the same when moves have different costs, always growing from the closest unfinished cell.
Why it works
BFS never reaches a cell by a long path before a short one, because it finishes each ring before starting the next. That guarantee is why it finds the shortest path. The cost is that it searches in every direction, even away from the goal.
Worked example: No walls
From (0, 0) to (4, 3), moving up, down, left or right.
- Every path needs 4 moves across and 3 up.
Answer: 7 moves.
Common mistake
Counting cells on the path, including the start, instead of moves. Seven moves visit eight cells.
The Math Ladder's shortest-paths topic covers Dijkstra's algorithm on general graphs.