Multi-Source BFS

Multi-Source BFS is a tiny but powerful variant of Breadth-First Search (BFS) in which the queue is initialised with multiple source vertices at distance 0 instead of a single source. The result, after the BFS completes, is a distance map giving for every vertex v the distance from v to the nearest source — all in the same O(V + E) time as a single-source BFS. Conceptually, multi-source BFS is identical to plain BFS run on a slightly larger graph in which all real sources have been replaced by a single virtual “super-source” vertex with zero-weight edges to each real source. This pattern is the algorithmic core of an entire class of grid problems — “Rotting Oranges” (LeetCode 994), “Walls and Gates” (LeetCode 286), “01 Matrix” (LeetCode 542) — and it is far cheaper than running a separate BFS from each source and taking the minimum (which would be O(k × (V + E)) for k sources, often blowing up to O(V²) on grids).

1. Intuition — Multiple Fires Spreading Through a Forest

Imagine a forest where several lightning strikes start fires simultaneously. Each minute, every burning tree ignites all its non-burning neighbours. The question: at any later moment, for every tree, how long until it catches fire?

If you tracked each fire separately, you’d get a “distance from fire #1” map, a “distance from fire #2” map, and so on — and the answer for each tree is the minimum across all fires. That’s correct but wasteful: you’ve simulated k separate fires when really there’s one expanding wavefront that cares only about which tree was reached, not which fire it came from.

Multi-source BFS treats the problem as a single expanding wavefront: time 0 = all initial fires, time 1 = everything adjacent to a fire, time 2 = everything two steps from any fire, etc. The frontier at time t is exactly the set of trees whose distance-to-nearest-fire is t. One BFS, total time O(V + E), gives you the full map.

The trick that makes this work — and makes it correct — is the virtual super-source: imagine a phantom vertex ★ connected by zero-cost edges to every real source. A standard single-source BFS from ★ would visit all real sources at distance 0, then their neighbours at distance 1, etc. Initialising the BFS queue with all real sources (rather than ★ itself) is a notational shortcut that produces identical distances and avoids materialising the phantom node. We’ve simulated ★ without ever putting it in our adjacency list.

2. Tiny Worked Example — Rotting Oranges

Given a 3×4 grid where 2 = rotten orange, 1 = fresh orange, 0 = empty cell:

2 1 1 0
1 1 0 1
0 1 1 2

Each minute, every rotten orange rots all 4-adjacent fresh oranges. How many minutes until no fresh oranges remain (or -1 if some can never be reached)?

Step 0 — initialise queue with both rotten oranges at time 0:

Queue: [(0,0,t=0), (2,3,t=0)]
Distances:
  d[0][0] = 0 (rotten)
  d[2][3] = 0 (rotten)
  everything else = ∞

Step 1 — pop (0,0), push fresh neighbours (0,1) and (1,0) at t=1. Pop (2,3), push fresh neighbour (2,2) at t=1. (Cell (1,3) is fresh, would be pushed at t=1.)

Queue after step 1: [(0,1,1), (1,0,1), (2,2,1), (1,3,1)]
Distances:
  d[0][0]=0  d[0][1]=1  d[0][2]=∞  d[0][3]=0(empty,skip)
  d[1][0]=1  d[1][1]=∞  d[1][2]=0(empty)  d[1][3]=1
  d[2][0]=0  d[2][1]=∞  d[2][2]=1  d[2][3]=0

Step 2 — pop the four t=1 nodes. New fresh neighbours pushed at t=2:

• (0,1) → push (0,2) at t=2
• (1,0) → push (1,1) at t=2
• (2,2) → push (2,1) at t=2
• (1,3) → no fresh neighbours

Step 3 — pop the three t=2 nodes. (1,1) has no fresh neighbours left except already-queued (0,1). Done.

Final time = 2 minutes. Verify by hand: yes, the cell furthest from any rotten orange is (0,2) or (1,1) or (2,1), each exactly 2 steps from a source. ✓

If we had run two separate BFS’s — one from (0,0), one from (2,3) — we’d visit each cell up to twice. Multi-source BFS visits each cell exactly once, regardless of how many sources we started with.

3. Pseudocode

multi_source_bfs(graph, sources):
    distance := map; distance[s] := 0 for every s in sources
    queue := empty FIFO; enqueue every s in sources
    while queue is not empty:
        u := dequeue
        for each neighbour v of u:
            if v not in distance:
                distance[v] := distance[u] + 1
                enqueue v
    return distance

The only difference from single-source BFS is the initialisation step. Everything else — the FIFO discipline, the visited check, the layer property — is unchanged.

4. Python Implementation

from collections import deque
 
def multi_source_bfs(graph, sources):
    """
    graph: dict node -> iterable of neighbours
    sources: iterable of nodes that all start at distance 0
    Returns: dict node -> distance to nearest source (only reachable nodes)
    """
    dist = {s: 0 for s in sources}
    q = deque(sources)
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

That’s the entire algorithm — eight lines. The compactness hides the conceptual leverage.

Grid version (the most common interview shape)

def multi_source_bfs_grid(grid, source_predicate, blocked_predicate):
    """
    grid: 2-D list (or list of strings)
    source_predicate(r, c): True if (r, c) is a source
    blocked_predicate(r, c): True if (r, c) is impassable (walls, etc.)
    Returns: 2-D dist matrix; -1 for unreachable cells.
    """
    R, C = len(grid), len(grid[0])
    dist = [[-1] * C for _ in range(R)]
    q = deque()
    for r in range(R):
        for c in range(C):
            if source_predicate(r, c):
                dist[r][c] = 0
                q.append((r, c))
    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # 4-neighbour
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C \
               and dist[nr][nc] == -1 \
               and not blocked_predicate(nr, nc):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

For Rotting Oranges (LC 994):

def oranges_rotting(grid):
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        r, c, t = q.popleft()
        minutes = max(minutes, t)
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                q.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

Note the in-place modification of grid to mark visited (1 → 2) — this avoids needing a separate visited matrix and is idiomatic for grid BFS.

5. Complexity

For a graph with V vertices and E edges, regardless of how many sources k:

• Time: O(V + E). Every vertex is enqueued at most once and dequeued at most once. Every edge is examined at most twice (once from each endpoint, in undirected graphs). The number of sources k does not appear in the asymptotic bound — it just changes how the queue is seeded.
• Space: O(V). The queue and the distance map each hold up to V entries.

For an R × C grid with 4-neighbour adjacency, V = R·C and E = O(R·C), so the algorithm is O(R·C) — linear in the number of cells.

Compare to running k separate BFS’s

If you naively ran a single-source BFS from each source separately and took the minimum:

• Time: O(k × (V + E)). For k = O(V) sources (e.g., a grid where most cells are sources), this becomes O(V × (V + E)) = O(V²) for sparse graphs, or O(V³) for dense — catastrophically worse.
• Space: usually O(V) if you accumulate the minimum, but you’ve done k times the work.

The win is enormous in problems where the source set is large. Walls and Gates (LC 286) on an n × n grid full of gates would be O(n²) with multi-source BFS but O(n⁴) with naive per-gate BFS — the difference between solving a 1000×1000 grid in a second versus an hour.

6. Why It Works — Correctness Proof

Claim: after multi-source BFS terminates, distance[v] equals min_{s ∈ sources} d(s, v) for every reachable vertex v, where d(s, v) is the unweighted-shortest-path distance from s to v.

Proof. Construct a virtual graph G' from G by adding one new vertex ★ and one zero-weight edge (★, s) for each source s. (Treat zero-weight edges as still counting as one BFS step but conceptualise them as instantaneous.) Run a single-source BFS from ★ in G'. By the standard BFS correctness proof (see Breadth-First Search §7), dist_{G'}(★, v) = shortest-path distance from ★ to v.

Any shortest path from ★ to v in G' must take exactly one zero-weight edge from ★ to some source s, then a real path from s to v. Its length is 0 + d(s, v) = d(s, v). The shortest path is achieved at the source s minimising d(s, v), so dist_{G'}(★, v) = min_s d(s, v).

Multi-source BFS as described is identical to BFS-from-★-in-G', with two cosmetic differences: (a) we never materialise ★, just enqueue all sources at distance 0; (b) we offset by 1 implicitly because the zero-weight edges from ★ are “free.” Both differences vanish under the algorithmic substitution, so the distances are identical. ∎

The crucial insight: the layer property of BFS (everything at distance k is dequeued before anything at distance k+1) generalises to multi-source because all sources start in the same layer (0), so the FIFO discipline still propagates layer-by-layer outward. The frontier at time t is exactly {v : min_s d(s, v) = t}.

7. Canonical Interview Problems

7.1 Rotting Oranges (LeetCode 994)

Already covered in §2 and §4. The canonical interview question. Watch for: “what if no rotten oranges initially?” (return 0 if no fresh either, else -1) and “what if some fresh orange is unreachable?” (return -1).

7.2 Walls and Gates (LeetCode 286)

Given an m × n grid where each cell is 0 = gate, 2147483647 = empty room, -1 = wall, fill each empty room with the distance to its nearest gate. Multi-source BFS from all gates simultaneously — the most natural application of the pattern.

def walls_and_gates(rooms):
    R, C = len(rooms), len(rooms[0])
    INF = 2147483647
    q = deque()
    for r in range(R):
        for c in range(C):
            if rooms[r][c] == 0:
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

7.3 01 Matrix (LeetCode 542)

For each cell of a 0/1 matrix, find the distance to the nearest 0. Multi-source BFS from all 0 cells. Trying to do this with single-source BFS from each 1 cell would be O((R·C)²) and time out.

7.4 Shortest Distance from All Buildings (LeetCode 317)

For each empty land cell, find the sum of shortest distances to all buildings. Here the multi-source pattern doesn’t directly work — you need separate BFS from each building because you sum across buildings rather than minimise. But the iteration across buildings is itself a multi-BFS pattern; just don’t conflate it with multi-source BFS.

7.5 As-Far-From-Land-As-Possible (LeetCode 1162)

Find the water cell whose distance to the nearest land cell is maximised. Multi-source BFS from all land cells; answer is the maximum value in the final distance grid.

7.6 Map of Highest Peak (LeetCode 1765)

A grid of land/water cells; assign heights such that water cells have height 0 and adjacent cells differ by at most 1. Multi-source BFS from all water cells gives the unique solution.

8. Variants and Generalisations

8.1 Weighted multi-source — Multi-Source Dijkstra

If the underlying graph has positive edge weights, replace BFS with Dijkstra’s Algorithm and seed the priority queue with all sources at distance 0. Time becomes O((V + E) log V). Same correctness argument via the virtual super-source.

8.2 Multi-Source 0-1 BFS

If edge weights are in {0, 1}, use the deque-based 01-BFS with multiple initial sources. Same O(V + E) cost.

8.3 Multi-target BFS

Symmetric problem: find the shortest distance from a single source to the nearest of several targets. Run plain single-source BFS from the source; stop the moment any target is dequeued. (Or run multi-source BFS from the targets and look up the source’s distance — equivalent.)

8.4 Multi-source DFS

Less common, but useful for “label every cell with which connected component it belongs to” when components are seeded from known anchors. Iterate sources in order, run DFS from each; cells get the label of the first source reaching them. This isn’t quite the same algorithm because DFS doesn’t have BFS’s layer-by-layer correctness guarantee, but it’s a related multi-seed pattern.

9. Pitfalls

9.1 Initialising sources one at a time inside the loop

# WRONG
q = deque()
for s in sources:
    q.append(s)
    dist[s] = 0
    while q:                   # consumes one source's BFS, not multi-source!
        ...

The while q belongs outside the source-initialisation loop. Otherwise you’re running k independent single-source BFS’s sequentially.

9.2 Forgetting to mark sources as visited at initialisation

# WRONG — sources can be re-discovered as neighbours
q = deque(sources)
# missing: dist initialisation for sources
while q:
    u = q.popleft()
    for v in graph[u]:
        if v not in dist:
            dist[v] = dist[u] + 1   # KeyError on first iteration: dist[u] doesn't exist
            q.append(v)

Sources must have dist[s] = 0 set before the loop starts. Otherwise the dist[u] lookup on the first pop fails.

9.3 Counting all sources as their own minimum-distance value

If a source has another source as a neighbour, both are still at distance 0. Don’t increment “from source A to source B” as distance 1 — they’re both seeds.

9.4 Using single-BFS-from-each instead

The most common naive solution to “01 Matrix” is to BFS from each 1 cell looking for the nearest 0. On an n × n grid mostly full of 1’s, this is O(n⁴) and times out. Spotting that the right direction is “BFS from the 0’s outward, pushing distances onto the 1’s” is the entire trick of the problem.

9.5 Forgetting -1 for unreachable cells

In Rotting Oranges, if there’s a fresh orange surrounded by empty cells with no path to any rotten orange, the answer must be -1, not “the maximum BFS depth.” Track unreached cells separately (count fresh and decrement on each rot).

9.6 Using list instead of collections.deque

Same pitfall as plain BFS: list.pop(0) is O(n). With multi-source BFS, the queue can start with thousands of sources, magnifying the slowdown. Use collections.deque.

9.7 Confusing “multi-source” with “multiple sources processed serially”

These are different. Multi-source BFS produces “distance to nearest source” in one pass. If you instead want “distance from each source to every vertex” (an all-pairs subset), you actually do need separate BFS per source — multi-source BFS would lose source identity.

10. Diagram — Wavefronts from Two Sources Meeting

flowchart LR
  S1[Source 1<br/>dist=0] -->|step 1| A[A<br/>dist=1]
  S1 -->|step 1| B[B<br/>dist=1]
  S2[Source 2<br/>dist=0] -->|step 1| C[C<br/>dist=1]
  S2 -->|step 1| D[D<br/>dist=1]
  A -->|step 2| E[E<br/>dist=2]
  B -->|step 2| F[F<br/>dist=2 from S1]
  C -->|step 2| F
  D -->|step 2| G[G<br/>dist=2]

What this diagram shows. Two real sources S1 and S2 are both placed in the BFS queue at distance 0. The wavefront expands outward layer by layer; vertices A, B, C, D are all at distance 1 (each from its respective nearest source). Vertex F is reachable from both S1 (via B) and S2 (via C) at the same distance 2; either path establishes dist[F] = 2 and the second arrival is rejected by the visited check. The diagram makes vivid that multi-source BFS is not two independent searches — there’s one merged frontier, and the distance map records “distance to whichever source’s wavefront arrived first.” The implicit super-source is the joining node behind S1 and S2; it would sit at distance -0 to both.

11. Common Interview Problems

LeetCode #	Problem	Source set
994	Rotting Oranges	All initially-rotten oranges
286	Walls and Gates	All gates
542	01 Matrix	All 0 cells
1162	As Far From Land As Possible	All land cells
1765	Map of Highest Peak	All water cells
417	Pacific Atlantic Water Flow	Two multi-source BFS’s: one from each ocean
1091	Shortest Path in Binary Matrix	Single source — not multi-source, but easy to confuse
1311	Get Watched Videos by Your Friends at Level K	Layered BFS, single source — same pattern but not multi-source

Tell-tale phrasing for multi-source BFS: “for every cell, find the distance to the nearest X” or “every X simultaneously spreads outward each step.”

12. Open Questions

• Is there a clean way to multi-source A* (priority-queue with several seeds)? Useful in pathfinding when many origins want shortest distance to nearest goal.
• What does multi-source BFS look like on a hypergraph? Likely the super-source trick still applies.
• On very large source sets (millions), is there a memory-saving variant that doesn’t materialise the full queue at once?

13. See Also

• Breadth-First Search — the parent algorithm; this note is a one-line modification of it
• Bidirectional BFS — different multi-frontier variant (one frontier per endpoint)
• 01-BFS — generalises to {0,1} edge weights
• Dijkstra’s Algorithm — multi-source generalises to weighted edges
• Topological Sort — Kahn’s algorithm is conceptually multi-source BFS seeded by all in-degree-0 nodes
• Big-O Notation
• SWE Interview Preparation MOC