Multi-Source BFS

A Bit of History

Multi-source BFS is a direct extension of Edward F. Moore's 1959 breadth-first search — the innovation is not a new traversal rule but a new way of thinking about the "start" of the search. The technique became especially popular through competitive programming communities in the 2000s and 2010s as a standard pattern for "nearest facility" style problems, and is formally equivalent to adding a single virtual super-source vertex connected to every real source with zero-weight edges — a trick with roots in classical network-flow reductions (Ford & Fulkerson, 1956) where multiple sources/sinks are similarly unified into one.

Working Principle: The Virtual Super-Source

Rather than running $k$ separate BFS traversals (one per source) and taking a pointwise minimum — costing $O(k \cdot (V + E))$ — multi-source BFS achieves the same result in a single $O(V + E)$ pass:

• Initialize the BFS queue with all source vertices simultaneously, each with distance 0.
• Proceed with standard BFS exactly as usual — pop from the front, relax unvisited neighbors, push to the back.
• Because every source starts at distance 0 and BFS explores level-by-level, the first time any vertex $v$ is reached, it's reached via the closest source — exactly the value we want.

Worked Example

The classic "Rotten Oranges" grid problem: cells are 0 (empty), 1 (fresh orange), or 2 (rotten orange). Each minute, every rotten orange rots its fresh neighbors. Find the minimum time for all oranges to rot, or -1 if impossible.

• Seed the BFS queue with every initially-rotten cell (multiple sources), each tagged with time 0.
• Process level-by-level: at each BFS "layer," every fresh neighbor of a rotten cell becomes rotten, tagged with time = current level + 1.
• The answer is the maximum time value assigned to any cell — the moment the "wave" of rot from all initial sources finally reaches the farthest fresh orange.
• If any fresh orange (1) remains unvisited after BFS completes, the answer is -1 (unreachable pocket).

Complexity Analysis

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V)$$

This is exactly the same complexity as single-source BFS — the number of sources $k$ never appears in the asymptotic bound, since every vertex and edge is still visited at most once total across the entire multi-source frontier expansion.

Implementation

from collections import deque

def multi_source_bfs(n, adj, sources):
    """
    n: number of vertices
    adj: adj[u] = list of neighbors
    sources: list of source vertices, all starting at distance 0
    Returns dist[] = distance to the NEAREST source for every vertex.
    """
    INF = float('inf')
    dist = [INF] * n
    q = deque()

    for s in sources:
        dist[s] = 0
        q.append(s)

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == INF:
                dist[v] = dist[u] + 1
                q.append(v)

    return dist

# Example: 6 vertices, sources = {0, 5}
n = 6
adj = [[] for _ in range(n)]
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

print("Distance to nearest source:", multi_source_bfs(n, adj, sources=[0, 5]))

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;
const int INF = numeric_limits<int>::max();

vector<int> multiSourceBFS(int n, vector<vector<int>>& adj, vector<int>& sources) {
    vector<int> dist(n, INF);
    queue<int> q;

    for (int s : sources) {
        dist[s] = 0;
        q.push(s);
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

int main() {
    int n = 6;
    vector<vector<int>> adj(n);
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,3},{3,4},{4,5}};
    for (auto& e : edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    vector<int> sources = {0, 5};
    vector<int> dist = multiSourceBFS(n, adj, sources);

    cout << "Distance to nearest source: ";
    for (int d : dist) cout << d << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class MultiSourceBFS {
    public static int[] solve(int n, List<List<Integer>> adj, int[] sources) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Deque<Integer> q = new ArrayDeque<>();

        for (int s : sources) {
            dist[s] = 0;
            q.add(s);
        }

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == Integer.MAX_VALUE) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0,1},{1,2},{2,3},{3,4},{4,5}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        int[] dist = solve(n, adj, new int[]{0, 5});
        System.out.println("Distance to nearest source: " + Arrays.toString(dist));
    }
}

Real-World Applications

Exercises

1. Solve the "Rotten Oranges" problem on a 5x5 grid with 3 initially-rotten cells scattered around the border.
2. Prove formally that multi-source BFS produces the same result as running single-source BFS from each source and taking the pointwise minimum.
3. Extend multi-source BFS to also record which source is nearest to each vertex (not just the distance).
4. Challenge: Adapt the technique to weighted graphs using a multi-source Dijkstra (seed the priority queue with all sources at distance 0 instead of the plain queue).

Limitations