Multi-Source BFS
Last Updated: April 5, 2026
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.
If you already understand single-source BFS from the previous chapter, multi-source BFS is a small but powerful extension. The algorithm is identical. The only thing that changes 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, just as it always does.
There is a useful mental model for understanding why this works. Imagine you create a "virtual super-source" node and connect it to every real source with a zero-weight edge. Running single-source BFS from this virtual node would first visit all real sources (at distance 0), and then expand outward from all of them. Multi-source BFS skips the virtual node and just places all sources directly at level 0. The result is exactly the same.
This means multi-source BFS finds the shortest distance from each cell to its nearest source. Not to a specific source, but to whichever source is closest. That is the key distinction from running BFS individually from each 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 textbook 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
Suppose you have a grid, and some cells are marked as "sources." You want to find 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 billion operations. Far too slow.
The Key Insight
All sources are at distance 0. If you put them all into the queue at the start, BFS will naturally expand 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. No need to run multiple BFS passes. One pass does everything.
This brings the time complexity down to O(m * n), same as a single BFS. You visit every cell exactly once, regardless of how many sources there are.
Think of it like dropping multiple stones into a pond at the same time. The ripples from each stone expand outward simultaneously. Where two sets of ripples meet, the boundary between them represents cells equidistant from two sources. Multi-source BFS computes the distance field for all of this 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.).
That is it. 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 to see multi-source BFS in action.
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
Notice how 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. If we had run BFS from each source separately, we would have gotten a different (incorrect) result, because the spread from (3,3) and (0,0) does not happen sequentially.
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 that you should memorize.
- 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.
Here is why:
- The initialization scan visits every cell once: O(m * n).
- During BFS, each cell is enqueued and dequeued at most once. For each cell, we check 4 neighbors, which is constant work per cell.
- Total work: O(m n) for the grid scan + O(m n) for the BFS = O(m * n).
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. This is the entire point of multi-source BFS: it collapses what would be O(k m n) with separate BFS passes into O(m * n).
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.
Comparison with Related Approaches
How does multi-source BFS stack up against alternative approaches? Here is a side-by-side comparison.
| 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 learn to spot these, the implementation is almost mechanical.
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 naturally 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.