How BFS shortest path works
Drop a stone in a pond and watch the ripple. It reaches every point one metre away before any point two metres away. Breadth-first search moves through a maze the same way: first every cell one step from the start, then every cell two steps away, ring after ring, until one of the rings touches the target. The number of the ring is the shortest distance.
The ripple is kept in a queue. Take the front cell, look at its four neighbours, and any neighbour that is open, inside the grid and not seen yet gets a distance one bigger than the current cell, a note of which cell it came from, and a place at the back of the queue. Because cells join the queue in distance order, they also leave it in distance order.
That note, the parent, is what turns a distance into a route. When the target is reached, follow the parents backwards to the start and you have walked the shortest path in reverse. The visualizer shows it being traced one cell at a time.
The loop shape
dist[start] = 0, queue = [start]. While the queue is not empty, pop the front cell and, for each open neighbour that has no distance yet, set its distance and parent and push it. If that neighbour is the target, stop: its distance is final the moment it is discovered, because everything discovered later is at least as far.
If the queue empties first, the target is walled off and there is no path. Note the badge on every cell above: it is the distance from the start, and the badges grow outward like the rings of the ripple.
A worked example: the maze
The example maze is 8 rows by 10 columns with walls in the way. From the top-left corner the search discovers cells ring by ring, and the target in the bottom-right corner is found at distance 20. Every explored cell shows its distance; the path traced back through the parents is highlighted.
The search visited 24 cells to find a path of 20 steps. That is the price of a guarantee: BFS cannot know which way the target lies, so it looks in every direction equally.
Where you'll meet it
- Games and robots. Moving a unit across a tile map, a robot vacuum planning around furniture, or a puzzle solver on a grid all start with grid BFS.
- Multi-source BFS. Start the queue with several cells at once and you get the nearest-source distance for every cell: LeetCode 994, Rotting Oranges, and 542, 01 Matrix.
- Beyond grids. The same loop finds the fewest hops between two people in a social network or the fewest edits between two words: any graph where every edge costs the same.
- Interviews. Shortest path in a binary matrix (1091, with diagonals), escaping a maze, and word ladders are all this algorithm.
Mistakes beginners make
- Marking cells when they leave the queue instead of when they enter. A cell can then be pushed several times, which is slow and, worse, can give it a wrong distance.
- Using DFS and hoping. The first path DFS finds is rarely the shortest.
- Using a stack by accident. In JavaScript,
pop()takes from the end, which turns the search into DFS. Take from the front with a real queue, or an index that moves forward. - Forgetting the no-path case. When the queue empties, return something that says “unreachable” rather than a distance.
Every grid search here visited each cell at most once. See how that growth compares with other algorithms: Big-O Playground →
BFS shortest path questions
Why does BFS find the shortest path?
Because it explores in rings. It finishes every cell at distance 1 before touching any cell at distance 2, and so on. So the first time the target is reached, it is reached from a cell one ring closer, and no shorter route can exist. This only holds when every step costs the same, which is true on a plain grid.
Why not DFS for the shortest path?
DFS commits to one direction and follows it as far as it can, so the first route it finds is usually a long detour. It can tell you whether a path exists, but not the shortest one, unless you try every path, which is far slower.
How do I get the actual path, not just its length?
Record a parent for each cell when you discover it: the cell you came from. When the target is reached, follow the parents back to the start and reverse the list. Distances alone are enough for the length; parents are what give you the route.
What if the moves have different costs, or diagonals are allowed?
Diagonal moves are fine as long as every move costs the same: add the four diagonal neighbours. LeetCode 1091 is that version and counts cells rather than moves. Different costs, such as mud that takes three steps, break BFS; that is where Dijkstra's algorithm comes in.