Multi-Source BFS

MNEMONIC Many seeds, one frontier.

THE PATTERN When “nearest of many” becomes one BFS

Plain BFS from a single source S labels every cell with its distance from S, because the frontier expands one equal-distance ring at a time. Multi-source BFS exploits the fact that a frontier is just a set of cells — it works identically whether that set starts with one cell or many.

The recipe: (1) initialize the queue with every source at distance 0 and mark them all visited; (2) run the ordinary layered BFS loop; (3) the first time a cell is dequeued onto, the current layer is its distance to the nearest source. Cells never reached stay at their sentinel (-1 / ∞).

KEY IDEA Many seeds, layer = distance

The single insight: a BFS frontier with k seeds expands in the same equal-distance rings as a frontier with one seed. So the layer index where a cell first joins the frontier is its shortest distance to whichever source is closest — by definition, the first ring to reach it came from the nearest seed.

COST One sweep, not k sweeps

For a grid of R×C cells, that is V = R·C and E = O(R·C) (≤ 4 edges per cell), so the whole thing is O(R·C) regardless of how many sources there are.

VARIANTS Three faces of the same trick

• Nearest-source distance.Fill every cell with its distance to the closest source. (01-Matrix, Walls & Gates.)
• Simultaneous spread / “minutes”. Count the number of layers until the frontier covers all required cells; return -1 if some never get reached. (Rotting Oranges.)
• Reverse multi-source from the borders.Seed the entire border as the source set and flood inward (reversing the movement rule) to find “cells that can reach the edge.” (Pacific–Atlantic, Surrounded Regions.)

RUN IT Many seeds, one frontier — distances fill in by layer

1function nearestZero(mat: number[][]): number[][] {
2  const R = mat.length, C = mat[0].length;
3  const dist = mat.map(row => row.map(v => (v === 0 ? 0 : -1)));
4  const visited = mat.map(row => row.map(v => v === 0));
5  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
6 
7  // 1. Seed the queue with ALL sources at distance 0.
8  let queue: [number, number][] = [];
9  for (let r = 0; r < R; r++)
10    for (let c = 0; c < C; c++)
11      if (mat[r][c] === 0) queue.push([r, c]);
12▶ 
13▶  // 2. Expand the frontier in layers.
14▶  while (queue.length) {
15▶    const next: [number, number][] = [];
16    for (const [r, c] of queue) {
17      for (const [dr, dc] of dirs) {
18        const nr = r + dr, nc = c + dc;
19        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
20        if (visited[nr][nc]) continue;     // first arrival = shortest
21        visited[nr][nc] = true;            // mark on ENQUEUE
22        dist[nr][nc] = dist[r][c] + 1;
23        next.push([nr, nc]);
24      }
25    }
26    queue = next;
27  }
28  // 3. Cells still at -1 were unreachable.
29  return dist;
30}

TRIGGERS When you see ___ → reach for ___

Reach for multi-source BFS whenever the answer is a shortest unweighted distance to the nearest of several starting points, or a count of steps for something to spread from many origins at once. The giveaway is the word nearest, any, or simultaneously attached to a set of sources.

RED FLAGSWhen it's NOT this pattern

• Edges have weights. BFS layers only equal distance when every step costs the same. With non-negative weights you need Dijkstra (or a 0-1 BFS / deque for weights in {0,1}), not plain multi-source BFS.
• There is exactly one source. Then it is just plain BFS — the multi-source machinery buys you nothing.
• You need the path, not the distance, from one specific source. Multi-source BFS blends all sources together; if you must know which source or the actual route, run a single-source BFS (and store parents).

TEMPLATE Grid multi-source BFS (nearest-source distance)

When → Fill every cell with its shortest distance to the nearest source. Seed allsources at distance 0, mark them visited, then expand in layers. The first arrival at any cell is its answer. (01-Matrix, Walls & Gates.)

// Multi-source BFS on a grid — distance to the NEAREST source.
// Classic: 01-Matrix (nearest 0), Walls & Gates (nearest gate).
function multiSourceBFS(grid: number[][]): number[][] {
  const R = grid.length, C = grid[0].length;
  const dist = grid.map(row => row.map(v => (isSource(v) ? 0 : -1)));
  const visited = grid.map(row => row.map(v => isSource(v)));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  // 1. SEED: push EVERY source before the first expansion.
  let queue: [number, number][] = [];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (isSource(grid[r][c])) queue.push([r, c]);  // distance 0
    }
  }

  // 2. EXPAND in layers — drain the whole ring, then move out one step.
  while (queue.length) {
    const next: [number, number][] = [];
    for (const [r, c] of queue) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;  // bounds
        if (visited[nr][nc]) continue;        // first arrival = shortest
        visited[nr][nc] = true;               // mark ON ENQUEUE
        dist[nr][nc] = dist[r][c] + 1;
        next.push([nr, nc]);
      }
    }
    queue = next;                             // advance to the next layer
  }

  // 3. Cells left at -1 are unreachable from any source.
  return dist;
}

TEMPLATE Reverse multi-source from all borders / oceans

When → “Which cells can reach the edge?” Flip the search: seed the queue with the entire border and flood inward, reversing the movement rule. Each cell the inward flood touches is one that could flow out. (Pacific–Atlantic, Surrounded Regions.)

// Reverse multi-source BFS: instead of "can X reach the border?",
// seed FROM the border and flood inward. (Pacific–Atlantic, Surrounded Regions.)
function reachableFromBorder(grid: number[][]): boolean[][] {
  const R = grid.length, C = grid[0].length;
  const reach = Array.from({ length: R }, () => new Array<boolean>(C).fill(false));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  // SEED the queue with EVERY border cell at once.
  const queue: [number, number][] = [];
  const seed = (r: number, c: number) => {
    if (!reach[r][c]) { reach[r][c] = true; queue.push([r, c]); }
  };
  for (let r = 0; r < R; r++) { seed(r, 0); seed(r, C - 1); }
  for (let c = 0; c < C; c++) { seed(0, c); seed(R - 1, c); }

  // Flood inward. For Pacific–Atlantic the climb condition reverses:
  // water flows DOWNHILL, so reverse-search only steps to HIGHER-or-equal cells.
  while (queue.length) {
    const [r, c] = queue.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
      if (reach[nr][nc]) continue;
      if (grid[nr][nc] < grid[r][c]) continue;  // reversed flow rule
      reach[nr][nc] = true;
      queue.push([nr, nc]);
    }
  }
  return reach;  // run once per ocean, AND the two results.
}

TEMPLATE Level-count "minutes" variant

When → You need the number of steps until the frontier covers everything, not per-cell distances. Process the queue one whole layer at a time, increment a counter per layer, and return -1 if anything is left unreached. (Rotting Oranges.)

// The "minutes / steps until everything is reached" variant — count LAYERS.
// Classic: Rotting Oranges (minutes until no fresh orange remains).
function minutesToFill(grid: number[][]): number {
  const R = grid.length, C = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  let queue: [number, number][] = [];
  let remaining = 0;                          // count cells still to reach
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);  // rotten = source
      else if (grid[r][c] === 1) remaining++;     // fresh = must be reached
    }
  }

  let minutes = 0;
  while (queue.length && remaining > 0) {
    const next: [number, number][] = [];
    for (const [r, c] of queue) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
        if (grid[nr][nc] !== 1) continue;     // only spread to fresh cells
        grid[nr][nc] = 2;                     // mark visited by mutating
        remaining--;
        next.push([nr, nc]);
      }
    }
    queue = next;
    minutes++;                               // one whole layer = one minute
  }

  return remaining === 0 ? minutes : -1;     // leftover fresh → impossible
}

PITFALL Marking visited at dequeue instead of enqueue

The signature multi-source bug. If you check visited only when you pop a cell, two different sources can both enqueue the same cell on different layers before either is processed — and the farther one stamps its (larger, wrong) distance second. Mark a cell visited and stamp its distance the moment it enters the queue, so the first (nearest) source wins permanently.

PITFALL Expanding before all sources are seeded

You must push every source into the queue at distance 0 before the first expansion step. If you start BFS after seeding only some sources (or seed them lazily as you go), the layers no longer correspond to distance from the nearest source and the distances come out wrong. Seed fully, then expand.

PITFALL Forgetting unreachable cells (return −1)

Cells with no path to any source stay at their sentinel value (-1 / Infinity). In the “minutes” variant this is the difference between a valid answer and -1: after the BFS, check whether any required cell was never reached and return -1 if so (e.g. fresh oranges that can never rot).

PITFALL 4-directional vs 8-directional neighbours

The spread direction set must match the problem. Most grid problems are 4-directional ([[1,0],[-1,0],[0,1],[0,-1]]); if diagonal adjacency counts, use the 8 deltas. Using the wrong neighbour set silently produces distances that are too large (or too small).

PROBLEMS