cf.completefrontend
GRAPHS · CORE

Multi-source BFS

Run one BFS from many start points at once to find each cell's distance to its nearest start.

Time O(rows * cols)Space O(rows * cols)5 practice problemsStep-through picture

The idea

Sometimes the question is not "how far is everything from this one point?" but "how far is everything from the nearest of these points?" For example: how far is each desk from the nearest printer?

You could run a separate BFS from each printer and keep the smallest distance, but with many printers that repeats a lot of work. Multi-source BFS puts every start point in the queue at the beginning, each with distance 0, and then runs one ordinary BFS.

Because all the starts begin together, the search spreads from all of them in rings at the same speed. The first ring to reach a cell comes from the closest start, so each cell gets the distance to its nearest start in a single pass.

An everyday example

Several stones dropped into a pond at once

Drop five stones into a still pond at the same moment. Each makes a ring of ripples that grows at the same speed. Any point on the water is first touched by the ripple from the closest stone. Where two ripples meet, they stop, because the water there has already moved.

How the example maps to the code
In the exampleIn the code
The stonesCells marked "S", all with dist[r][c] = 0
Ripples growing at the same speedBFS handling the queue ring by ring
The first ripple to touch a pointThe first time dist[nr][nc] is set
Rocks sticking out of the waterWall cells "#" that are skipped

From the slow way to multi-source bfs

  1. Say you need each cell's distance to the nearest of several sources. The obvious way is one BFS per source, keeping the smallest distance per cell. With k sources that is k full searches: 500 sources on a 300 by 300 grid means about 45 million cell visits.
  2. Notice that the question never asks which source is nearest, only how far. All sources play the same role, so there is no reason to treat them one at a time.
  3. Imagine one extra, invisible cell with an edge to every source. A single BFS from it would reach every source in ring 1, their neighbors in ring 2, and so on. Every cell's ring number would be one more than its distance to the nearest source.
  4. You don't need to build that cell. Starting the queue with all sources already in it, each at distance 0, is exactly the state that BFS would reach after handling the invisible cell. Then run a normal BFS. That is multi-source BFS.

How it works

  1. Make dist, a grid of -1 values the same size as grid.
  2. Scan every cell. For each source cell ("S"), set its dist to 0 and add it to the queue.
  3. Run a normal BFS: take the cell at queue[head].
  4. For each of its four neighbors, skip it if it is outside the grid, a wall ("#"), or already has a distance.
  5. Otherwise set dist[nr][nc] = dist[r][c] + 1 and add it to the queue.
  6. When the queue is used up, dist holds each cell's distance to its nearest source, and -1 where no source can reach.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function multiSourceBfs(grid) {
  2. const rows = grid.length;
  3. const cols = grid[0].length;
  4. const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  5. const queue = [];
  6. for (let r = 0; r < rows; r++) {
  7. for (let c = 0; c < cols; c++) {
  8. if (grid[r][c] === "S") {
  9. dist[r][c] = 0;
  10. queue.push([r, c]);
  11. }
  12. }
  13. }
  14. for (let head = 0; head < queue.length; head++) {
  15. const [r, c] = queue[head];
  16. for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
  17. const nr = r + dr;
  18. const nc = c + dc;
  19. if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
  20. if (grid[nr][nc] === "#" || dist[nr][nc] !== -1) continue;
  21. dist[nr][nc] = dist[r][c] + 1;
  22. queue.push([nr, nc]);
  23. }
  24. }
  25. return dist;
  26. }

How fast it is

TimeO(rows * cols)
Extra memoryO(rows * cols)

Each cell joins the queue at most once and checks 4 neighbors, however many sources there are. dist and the queue each hold up to one entry per cell.

  • Best caseO(rows × cols)

    Even with no sources, the first double loop reads every cell once to look for them.

  • Average caseO(rows × cols)

    Every open cell is queued once and checks 4 neighbors, however many sources there are.

  • Worst caseO(rows × cols)

    The whole grid is open, so every cell is queued and handled.

Common mistakes

  • Running a separate BFS for each source. It gives the right answer but can be thousands of times slower.
  • Adding sources to the queue one at a time and running BFS between them. All sources must be in the queue before the first cell is handled.
  • Forgetting to check for cells that are never reached when the question asks how long until everything is covered.
  • Returning the largest distance when there are no sources at all. Decide what that case should return and handle it first.

When to use it

Look for these clues in a problem:

  • There are many sources, and you need each cell's distance to the nearest one.
  • Something spreads from several places at once, one step per minute: fire, a virus, rot, an outage.
  • The question asks how long until everything is reached, or the farthest any cell is from all sources.
  • Running a BFS from every source would be too slow.

Check yourself

Answer each one in your head first, then open it.

Why must all sources be queued before any cell is handled?

If the first source's search ran alone first, cells near the second source would get large distances from the first one. The dist !== -1 check would then stop the second source from fixing them.

How many cells were queued in the trace, and why that number?

Ten: the two sources plus eight other open cells. Every open cell is queued once, and the two walls never are.

Does adding more sources make it slower?

No. Each cell is still queued at most once. More sources usually make it end sooner, because the rings have less ground to cover.

What is the answer to "how many steps until every open cell is reached" for the trace's grid?

3, the largest value in dist, at cell (2,1). No open cell is left at -1.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Think of the invisible start cell again. Plain BFS from it would handle that cell first and queue every source with ring number 1. Multi-source BFS starts in exactly that state, with every number one lower. So everything proven about BFS carries over: cells leave the queue in order of distance, and each cell's first distance is the shortest.

In this grid, the shortest distance from the invisible cell to a cell is 1 plus the shortest distance from the nearest source, because every path from the invisible cell starts with a free hop to some source. So dist[r][c] is the distance to the nearest source, walking only through open cells.

It ends because each cell is queued at most once: its dist stops being -1 at the moment it is queued. Walls are never queued, and cells with no open path to any source are never reached, so they keep -1.

Going deeper

3 more ideas

Why one BFS is enough

Imagine one extra, invisible cell that connects to every source with a step of length 0. A plain BFS from that invisible cell would first reach all sources at distance 0, then their neighbors at distance 1, and so on. Putting every source in the queue at the start is exactly that BFS, without building the extra cell. So the usual BFS rule holds: each cell's first distance is the shortest one.

Turning distances into a time

For "how many minutes until every cell is reached?", the answer is the largest number in dist. If any cell that should be reached is still -1, the answer is "never", usually written -1. If there are no cells to reach at all, the answer is 0.

Cost compared with many separate searches

With k sources, running BFS from each one costs O(k * rows * cols). Multi-source BFS visits each cell once, so it costs O(rows * cols) no matter how many sources there are.

Work it by hand

Every step in a table, with why

Distance to the nearest S on a 3 by 4 grid with a wall column in the middle (# is a wall).

grid = ["S.#.", "..#S", "...."]

StepHandled [r, c]Its distNewly setqueue waitingWhy
1--(0,0)=0, (1,3)=0(0,0) (1,3)The scan finds both sources, gives them distance 0, and queues them before any cell is handled.
2(0,0)0(1,0)=1, (0,1)=1(1,3) (1,0) (0,1)The left source reaches its two open neighbors.
3(1,3)0(2,3)=1, (0,3)=1(1,0) (0,1) (2,3) (0,3)The right source does the same. Ring 1 is now complete on both sides of the wall.
4(1,0)1(2,0)=2, (1,1)=2(0,1) (2,3) (0,3) (2,0) (1,1)Ring 2 starts. (0,0) is skipped because it already has a distance.
5(0,1)1none(2,3) (0,3) (2,0) (1,1)Right is the wall (0,2), down (1,1) was just set, and left is a source.
6(2,3)1(2,2)=2(0,3) (2,0) (1,1) (2,2)The right side spreads left along the bottom row, under the wall.
7(0,3)1none(2,0) (1,1) (2,2)Its only open neighbor, (1,3), is a source. The wall (0,2) blocks it from the left side.
8(2,0)2(2,1)=3(1,1) (2,2) (2,1)(2,1) gets distance 3, the largest in the grid.
9(1,1)2none(2,2) (2,1)Every open neighbor already has a distance. Right is the wall (1,2).
10(2,2)2none(2,1)(2,1) would also get 3 from here, but it is already set, so nothing changes.
11(2,1)3noneemptyThe last cell finds nothing new. The queue is used up.

It returns [[0, 1, -1, 1], [1, 2, -1, 0], [2, 3, 2, 1]]. Each of the 10 open cells was handled exactly once. The walls stay -1, and the slowest cell to reach is (2,1), at distance 3.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Multi-source BFSO(rows × cols)O(rows × cols)You need every cell's distance to the nearest of many sources, and every step costs the same.
One BFS per sourceO(k · rows × cols)O(rows × cols)You need the distance to each source separately, not just to the nearest one.
Two-pass distance sweepO(rows × cols)O(rows × cols)There are no walls, so the distance is just rows plus columns apart. A top-left sweep and a bottom-right sweep give it without a queue.
Multi-source DijkstraO(e log n)O(n + e)Steps have different costs, such as slow terrain, so a plain queue no longer gives distances in order.

Extra memory: O(rows × cols): dist has one number per cell, and the queue can hold up to one entry per cell.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Multi-source BFS and the other approaches, on a scale where each line up is 10 times more steps.
  • Multi-source BFS, Two-pass distance sweep O(rows × cols)
  • One BFS per source O(k · rows × cols)
  • Multi-source Dijkstra O(e log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Multi-source BFS1001 million1 trillion
One BFS per source1,0001 billionmore than a quadrillion
Two-pass distance sweep1001 million1 trillion
Multi-source Dijkstra339,96620 million

Inputs that need care

5 tricky inputs
No S at all
The queue starts empty, the BFS loop never runs, and every cell stays -1. If the question asks how long until everything is reached, decide that answer first.
Every cell is a source
Every dist is 0. The BFS loop still handles each cell once, but every neighbor already has a distance, so nothing changes.
A source closed in by walls
It reaches nothing. Cells beyond the walls can still be reached by other sources, or stay -1 if none can reach them.
A cell exactly as far from two sources
Whichever source's ring reaches it first sets it, but both would give the same number, so the distance is the same either way.
A problem where some open cells don't need to be reached, such as empty space in a spreading puzzle
Map the problem's symbols carefully: decide which cells can be walked through, which are walls, and which ones count when you ask whether everything was reached.

Variations and follow-ups

Twists interviewers add

Which source is nearest

Keep an owner grid and copy owner[r][c] into owner[nr][nc] when a cell is first reached. Each cell then knows the source whose ring got there first, which splits the grid into one region per source.

Time until everything is covered

Take the largest value in dist. If any cell that should be covered is still -1, the answer is "never", usually -1.

Distance to the nearest wall or edge

Use every wall cell as a source. The result is a distance map of the open space, which drawing tools use for outlines, glows, and finding the middle of a shape.

Sources on a general graph or with weights

On adjacency lists the code is the same: queue every source first. If moves have different costs, put every source into a Dijkstra heap at cost 0 instead.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "nearest" plus several starting points, or something spreading from many places at once: rot, fire, water, infection.
  • Explain it with the invisible cell: "queuing all sources at 0 is the same as one BFS from a cell joined to every source". It shows you know why it is correct, not just the trick.
  • Test by hand: no sources, a cell walled off from every source, and a cell exactly between two sources.
  • Expect "how many minutes until everything is covered?". Answer: the largest distance, or -1 if a cell that must be covered was never reached.

Where frontend code uses it

The same idea in real UI code
  • Map and floor-plan widgets that shade each tile by its distance to the nearest point of interest, such as an exit or a store.
  • Grid-based games in the browser, where enemies spread out from several spawn points or a fire spreads from several sparks.
  • Image tools that compute a distance map from the edges of a shape, used for effects like outlines and glows.

Related algorithms