The idea
Breadth-first search keeps a queue of vertices to expand. Because vertices leave the queue in order of distance, the first time a vertex is reached is along a shortest path, counted in edges.
It runs in O(V + E) and is the tool for shortest paths when every edge costs the same, including moves on a grid.
Starting with several sources in the queue at distance 0 gives each vertex its distance to the nearest source in a single pass.
Sample problem
542. 01 Matrix ↗ Medium
Given a grid of 0s and 1s, return for every cell the distance to the nearest 0. Neighbouring cells (up, down, left, right) are at distance 1.
mat = 0 1 1 1 output = 0 1 2 3
1 1 1 1 1 2 3 2
1 1 1 1 2 3 2 1
1 1 1 0 3 2 1 0Why the solution works
Running a search from every 1 to find its nearest 0 repeats the same work many times. Turn it around: search outwards from the 0s.
Breadth-first search visits cells in order of distance. If all the 0 cells are put in the queue first, at distance 0, the search spreads from them at once, and the first time a cell is reached is from its nearest 0.
The queue is what guarantees the order: everything at distance d leaves it before anything at distance d + 1.
Complexity: O(R · C) time and memory: each cell enters the queue once.
Watch out
- Set the distance when a vertex is pushed, not when it is popped, or it gets queued many times.
- BFS is only correct when all edges have equal weight. With weights 0 and 1 use a deque; otherwise Dijkstra.
- Check grid bounds before reading a cell.