Multi-source BFS is a variation of breadth-first search where you start from multiple sources at once instead of just one. All sources are added to the queue initially, and the search expands outward in layers, ensuring the shortest distance to each node or cell.

Multi-source BFS is a small extension of standard single-source BFS. The algorithm is identical. The only change is the initialization.

What Is Multi-Source BFS?

In standard BFS, you start from a single source node, add it to a queue, and explore its neighbors level by level. The FIFO queue guarantees that all nodes at distance d are processed before any node at distance d+1. This gives you shortest paths from that single source.

Multi-source BFS is the same algorithm, but instead of putting one node into the queue at the start, you put all source nodes into the queue at level 0. From there, BFS expands outward from all sources simultaneously, level by level. The result is the shortest distance from each cell to its nearest source, not to a specific source.

Real-World Applications

Forest fire simulation: Multiple fires break out at different locations. Flames spread to adjacent areas every time step. Multi-source BFS models how quickly the entire forest burns.
Network broadcast: A message originates at several servers. Each server forwards it to its neighbors. Multi-source BFS computes how many hops it takes for every node in the network to receive the message.
Nearest facility computation: Given a map with several hospitals, find the distance from every location to the nearest hospital. This is a direct multi-source BFS problem.
Social network influence: Multiple influencers post content simultaneously. How many "hops" until a piece of information reaches every user?
Game AI: In strategy games, multiple units spread control over territory simultaneously. The game engine uses multi-source BFS to compute influence zones.

These all share the same structure: multiple origins, simultaneous expansion, and the need to know the shortest distance from each point to its nearest origin.

The Core Idea

A common setup is a grid where some cells are marked as "sources" and the goal is the shortest distance from every cell to its nearest source.

The naive approach is to run a BFS from each source independently, computing the distance from that source to every cell, and then take the minimum across all sources. If there are k sources and the grid has mn cells, that costs O(k m * n). For a 1000x1000 grid with 500 sources, that is 500 million operations.

The Key Insight

All sources are at distance 0. If you put them all into the queue at the start, BFS expands outward from all of them at the same time. Level 1 contains all cells that are adjacent to any source. Level 2 contains all cells that are two steps from their nearest source. And so on.

Because BFS is FIFO and processes nodes in the order they were enqueued, the first time any cell is visited, it has been reached by the nearest source via the shortest path. A single pass produces the answer for every cell.

This brings the time complexity down to O(m * n), the same as a single BFS. Every cell is visited exactly once, regardless of how many sources there are.

A useful visual is multiple stones dropped into a pond at the same time. The ripples from each stone expand outward simultaneously. Where two sets of ripples meet, the boundary represents cells equidistant from two sources. Multi-source BFS computes that entire distance field in a single pass.

Visual Overview

The diagram below shows a grid with three sources (S). The colors represent the BFS level at which each cell is first reached.

Each level expands outward from all sources simultaneously. A cell at level 2 means its nearest source is exactly 2 steps away.

How It Works

The algorithm has three phases. The first is unique to multi-source BFS. The second and third are identical to standard BFS.

Algorithm Steps

Scan for sources: Walk through the entire input (grid, graph, etc.) and identify all source nodes. Add each source to the queue and mark it as visited with distance 0.
BFS expansion: While the queue is not empty, dequeue a node, look at its neighbors, and for each unvisited neighbor, mark it visited, record its distance (current distance + 1), and enqueue it.
Result extraction: When the queue is empty, every reachable cell has been assigned its shortest distance to the nearest source. Read off whatever the problem asks for (maximum distance, specific cell's distance, count of reachable cells, etc.).

The only difference from single-source BFS is step 1: instead of enqueuing one node, you enqueue all sources.

Step-by-Step Flowchart

Example Walkthrough: Rotting Oranges (LeetCode 994)

Let us trace through a concrete example.

Problem Setup

We have a 4x4 grid. The value 0 means empty, 1 means fresh orange, and 2 means rotten orange.

There are two rotten oranges: at (0,0) and (3,3). There are 8 fresh oranges. We need to find the minimum number of minutes until all fresh oranges are rotten.

Step-by-Step Trace

Both rotten oranges spread simultaneously. By minute 2, the expanding rot zones from the two sources have almost met in the middle. By minute 3, every fresh orange has been reached. Running BFS from each source separately and taking the per-cell minimum would produce the same final answer, but it would cost O(k m n) instead of O(m * n). Multi-source BFS speeds up the computation without changing the result.

Implementation

Here is a generic multi-source BFS implementation for grid problems. The function takes a grid, identifies all sources, and computes the shortest distance from each cell to its nearest source.

Code Explanation

The structure across all implementations is identical:

Initialization loop: We scan the entire grid looking for source cells. Every source gets enqueued with distance 0 and marked as visited. Non-source cells start with distance -1 (unreachable until BFS reaches them).
Directions array: The four-entry directions array encodes the four cardinal directions (right, left, down, up). This is a standard idiom for grid traversal.
BFS loop: We dequeue a cell, check its four neighbors, and for each valid unvisited neighbor, compute its distance as the current cell's distance plus one. Then we mark it visited and enqueue it.
No level tracking needed here: Unlike some BFS problems where you need to count levels explicitly, the distance array itself tracks the level for each cell. Each cell's distance is its parent's distance plus one.

Common Mistakes:

Forgetting to mark sources as visited during initialization. This causes sources to be re-enqueued when a neighbor processes them, leading to incorrect distances.
Using a data structure with O(n) dequeue operations for the queue. For example, using a plain list with removal from the front in Python is O(n) per operation, which turns O(mn) BFS into O((mn)^2). Use a deque or a pointer-based approach instead.
Checking grid boundaries after accessing the array instead of before. Always validate indices before reading the grid cell.

Complexity Analysis

Time Complexity

Overall: O(m * n) for a grid, or O(V + E) for a general graph.

The initialization scan visits every cell once: O(m * n).
During BFS, each cell is enqueued and dequeued at most once, with constant work (4 neighbor checks) per cell.

The number of sources does not affect the time complexity. Whether you have 1 source or 10,000 sources, the BFS still visits each cell exactly once.

Space Complexity

Overall: O(m * n)

The distance array: O(m * n).
The visited array: O(m * n). (Can be avoided if you modify the grid in place.)
The queue: O(m * n) in the worst case, when all cells are sources or when the BFS frontier spans the entire grid.

The table below compares multi-source BFS against alternative approaches.

Approach	Time Complexity	Space Complexity	Correctness	When to Use
Multi-source BFS	O(V + E)	O(V)	Correct for unweighted graphs	Multiple sources, uniform edge weights, simultaneous expansion
Separate BFS from each source	O(k * (V + E))	O(V)	Correct but slow	Very few sources (k is small), or when you need per-source distances
Dijkstra from virtual super-source	O((V + E) log V)	O(V)	Correct for weighted graphs	Sources at different "starting costs," weighted edges
BFS from single source	O(V + E)	O(V)	Wrong for multi-source problems	Only one source exists

When to Choose Multi-Source BFS

All sources are equivalent (same starting distance of 0).
The graph is unweighted, or all edges have the same weight.
You need the shortest distance from each node to its nearest source.

When NOT to Use Multi-Source BFS

Sources have different starting costs (e.g., some fires started earlier than others). In this case, you need Dijkstra with a priority queue.
You need the shortest distance from each node to a specific source, not just the nearest one. In that case, run BFS from each source individually.
The graph has weighted edges with varying weights. Multi-source BFS assumes all edges have equal weight.

Common Patterns and Applications

Multi-source BFS appears in several recognizable patterns in interview problems. Once you can spot the pattern, the implementation follows the same template each time.

Pattern 1: Simultaneous Spread

Problem type: Multiple entities spread to adjacent cells each time step. Find how long until everything is reached (or whether it is possible).

How multi-source BFS helps: Enqueue all spreading entities at level 0. Each BFS level represents one time step. The answer is the maximum level reached (or -1 if some cells are unreachable).

Examples: Rotting Oranges (LC 994), where rotten oranges spread rot. Shortest Bridge (LC 934), where you find all cells of one island, then BFS-expand toward the other island.

Pattern 2: Distance from Nearest Source

Problem type: Given a grid with some special cells, compute the shortest distance from every cell to its nearest special cell.

How multi-source BFS helps: Enqueue all special cells as sources. BFS computes the shortest distance from each cell to whichever source is closest.

Examples: 01 Matrix (LC 542), where you find the distance from each cell to the nearest 0. Walls and Gates (LC 286), where you find the distance from each empty room to the nearest gate. Map of Highest Peak (LC 1765), where you assign heights based on distance from water cells.

Pattern 3: Boundary Expansion

Problem type: Start from all boundary cells and expand inward.

How multi-source BFS helps: Enqueue all boundary cells as sources. BFS expands inward, and you can use the distance values or the visited set for further processing.

Examples: Surrounded Regions (LC 130), where you mark all O cells reachable from the boundary. Pacific Atlantic Water Flow (LC 417), where you expand from ocean boundaries inward.

Key Takeaways

Multi-source BFS seeds the queue with every source at distance 0 and marks each one visited during initialization, then runs the same FIFO loop as standard single-source BFS. The only difference from single-source BFS is that step.
Because all sources start at level 0 and expand together, the first time BFS reaches a cell it has arrived from the nearest source along the shortest path. A single pass produces the minimum distance from each node to its nearest source.
The time complexity is O(V + E) for a graph or O(m * n) for a grid, and it does not depend on the number of sources. Visiting each cell once costs the same whether there is 1 source or 10,000.
Running a separate BFS from each of k sources and taking the per-cell minimum gives the same answer at O(k * (V + E)), so multi-source BFS is the faster choice when sources share a starting distance and edges are unweighted.
Use multi-source BFS for simultaneous spread problems like Rotting Oranges (LC 994) and for nearest-source distance problems like 01 Matrix (LC 542) and Walls and Gates (LC 286). Switch to Dijkstra from a virtual super-source when sources have different starting costs or edges carry varying weights.

Quiz

Multi-Source BFS Quiz

10 quizzes