Multi-Source BFS
Standard BFS answers "how far is everything from this one starting point?" Multi-source BFS answers a harder question: "how far is everything from the nearest starting point?" And the trick is embarrassingly simple --- push all the starting points into the queue at time 0 and run normal BFS. One change to the initialization, zero changes to the algorithm.
The Core Idea
Single-source BFS: one cell enters the queue at distance 0. The BFS wavefront expands outward in concentric rings.
Multi-source BFS: all source cells enter the queue at distance 0. Multiple wavefronts expand simultaneously. When two wavefronts collide, the cell has already been claimed by whichever source was closer. The dist array naturally records the distance to the nearest source.
queue<pair<int,int>> q;
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
if (grid[i][j] == '*') {
dist[i][j] = 0;
q.push({i, j});
}
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < H && nc >= 0 && nc < W
&& dist[nr][nc] == -1 && grid[nr][nc] != '#') {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
Key insight. Multi-source BFS is equivalent to adding a virtual super-source node \(S\) connected to every real source with a zero-weight edge, then running single-source BFS from \(S\). You never actually create \(S\) --- pushing all sources at distance 0 achieves the same effect.
Trace: Two Sources
Grid (5x5), sources at (0,0) and (4,4), walls at (2,2):
BFS expansion (distance from nearest source):
| Step | Queue contents (front first) | Cells assigned |
|---|---|---|
| Init | (0,0)=0, (4,4)=0 | dist[0][0]=0, dist[4][4]=0 |
| 1 | (0,1)=1, (1,0)=1, (4,3)=1, (3,4)=1 | 4 new cells at distance 1 |
| 2 | (0,2)=2, (1,1)=2, (2,0)=2, (4,2)=2, (3,3)=2, (2,4)=2 | 6 new cells at distance 2 |
| 3 | ... | Wavefronts collide around the center |
Final distance grid:
Notice the symmetry. Each cell's value is the distance to whichever source is closer.
CSES Monsters --- Detailed Walkthrough
Problem: A player starts at A on a grid. Monsters start at M positions. Each turn, the player moves one step, then all monsters move one step toward the player (optimally). The player escapes by reaching any boundary cell. Can the player escape? If yes, print the path.
Key realization: Monsters move optimally, which means they spread like a BFS wavefront. The player can only enter a cell if they arrive there strictly before any monster.
Algorithm:
- Run multi-source BFS from all monster positions. This gives
mdist[r][c]= the earliest time any monster can reach cell \((r, c)\). - Run single-source BFS from the player's start. The player can enter cell \((nr, nc)\) at time \(t+1\) only if
mdist[nr][nc]is either unreachable by monsters (\(-1\)) or strictly greater than \(t+1\). - If the player's BFS reaches any boundary cell, the answer is YES.
// Step 1: Monster BFS
memset(mdist, -1, sizeof(mdist));
queue<pair<int,int>> q;
for (auto [mr, mc] : monsters) {
mdist[mr][mc] = 0;
q.push({mr, mc});
}
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < H && nc >= 0 && nc < W
&& mdist[nr][nc] == -1 && grid[nr][nc] != '#') {
mdist[nr][nc] = mdist[r][c] + 1;
q.push({nr, nc});
}
}
}
// Step 2: Player BFS
memset(pdist, -1, sizeof(pdist));
pdist[sr][sc] = 0;
q.push({sr, sc});
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (r == 0 || r == H-1 || c == 0 || c == W-1) {
// reached boundary — reconstruct path and print
break;
}
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < H && nc >= 0 && nc < W
&& pdist[nr][nc] == -1 && grid[nr][nc] != '#'
&& (mdist[nr][nc] == -1
|| pdist[r][c] + 1 < mdist[nr][nc])) {
pdist[nr][nc] = pdist[r][c] + 1;
par[nr][nc] = d; // for path reconstruction
q.push({nr, nc});
}
}
}
Monsters Trace
Grid (5x5):
Monster at (0,2). Player at (2,2).
Monster BFS:
| Distance | Cells reached |
|---|---|
| 0 | (0,2) |
| 1 | (0,1), (0,3), (1,2) |
| 2 | (1,1), (1,3), (2,2)* |
| 3 | (1,0), (1,4), (2,1), (2,3), (3,2) |
| 4 | (2,0), (2,4), (3,1), (3,3), (4,1) |
| 5 | (3,0), (3,4), (4,2) |
*Monster reaches (2,2) at time 2. Player starts there at time 0, so the player can leave before the monster arrives.
Player BFS: The player at (2,2) at time 0 tries to move. They can enter (2,1) at time 1 only if 1 < mdist[2][1] = 3. Yes. They can reach (2,0) at time 2 only if 2 < mdist[2][0] = 4. Yes. Cell (2,0) is a boundary cell --- player escapes.
Gotcha. The condition is strictly less than, not less-or-equal. If the player and a monster arrive at the same time, the monster catches the player. The player must arrive before the monster.
LC 994 --- Rotten Oranges
Problem: Grid with 0 (empty), 1 (fresh orange), 2 (rotten orange). Each minute, every fresh orange adjacent to a rotten one becomes rotten. Return the number of minutes until no fresh oranges remain. Return \(-1\) if impossible.
This is textbook multi-source BFS. All rotten oranges are sources at time 0. BFS spreads the rot. The answer is the maximum distance assigned, or \(-1\) if any fresh orange is never reached.
int orangesRotting(vector<vector<int>>& grid) {
int H = grid.size(), W = grid[0].size();
queue<pair<int,int>> q;
int fresh = 0;
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) {
if (grid[i][j] == 2) q.push({i, j});
if (grid[i][j] == 1) fresh++;
}
int time = 0;
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
while (!q.empty() && fresh > 0) {
int sz = q.size();
while (sz--) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < H && nc >= 0 && nc < W
&& grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
q.push({nr, nc});
}
}
}
time++;
}
return fresh == 0 ? time : -1;
}
Rotten Oranges Trace
Grid:
| Minute | Newly Rotten | Fresh Remaining |
|---|---|---|
| 0 | (0,0) initial | 7 |
| 1 | (0,1), (1,0) | 5 |
| 2 | (0,2), (1,1) | 3 |
| 3 | (2,1), (1,2)* | 1 |
| 4 | (2,2) | 0 |
*Wait --- (1,2) is empty (value 0). It stays 0 and never rots. Let me re-trace. (1,2) is 0 in the original grid, so it's skipped. The fresh orange at (2,2) is reached from (2,1) at minute 4.
Answer: 4.
LC 542 --- 01 Matrix
Problem: Given a binary matrix, find the distance of the nearest 0 for each cell.
All 0-cells are sources. Multi-source BFS gives the distance from each cell to the nearest 0.
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int H = mat.size(), W = mat[0].size();
vector<vector<int>> dist(H, vector<int>(W, -1));
queue<pair<int,int>> q;
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
if (mat[i][j] == 0) {
dist[i][j] = 0;
q.push({i, j});
}
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < H && nc >= 0 && nc < W
&& dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
return dist;
}
Key insight. If you tried BFS from each 1-cell individually, you'd get \(O(H^2 W^2)\) time. Multi-source BFS from all 0-cells solves it in \(O(H \times W)\). That's the power of reversing the direction: instead of "each cell searches for the nearest source," you let "all sources expand outward simultaneously."
The Pattern
Every multi-source BFS problem follows the same template:
- Identify all source cells.
- Push them all into the queue with distance 0.
- Run standard BFS.
- The
distarray now holds the answer.
The only variation is what you do with the distance array afterward. Sometimes you want the max (Rotten Oranges). Sometimes you compare it against another BFS (Monsters). Sometimes you return it directly (01 Matrix).
Exercises
-
Manual trace. On a 4x4 grid with sources at
(0,0)and(3,3)and a wall at(1,1), draw the distance grid produced by multi-source BFS. Verify that each cell's distance equals its distance to the nearest source, routing around the wall. -
As Far from Land as Possible (LC 1162). Grid with 1 (land) and 0 (water). Find the water cell with the maximum distance to any land cell. How does multi-source BFS solve this in \(O(H \times W)\)?
-
Monsters edge case. In CSES Monsters, what if the player's starting cell is already on the boundary? They escape immediately with an empty path. What if a monster starts on the player's cell? The player is caught at time 0.
-
Multiple wavefronts. Can you use multi-source BFS to partition the grid into Voronoi regions --- each cell assigned to its nearest source? What additional information do you need to store?
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES Monsters | cses.fi/problemset/task/1194 | Medium |
| LC 994 --- Rotten Oranges | leetcode.com/problems/rotting-oranges | Medium |
| LC 542 --- 01 Matrix | leetcode.com/problems/01-matrix | Medium |
| LC 1162 --- As Far from Land as Possible | leetcode.com/problems/as-far-from-land-as-possible | Medium |