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:

• Multi-Source Initialization: Initialize the BFS queue with all source vertices simultaneously, each tagged with distance 0. Mark all initial sources as visited immediately.
• Unified Queue Traversal: Proceed with standard BFS exactly as usual — pop from the front, inspect unvisited neighbors, assign dist[neighbor] = dist[u] + 1, and push to the back.
• Earliest Arrival Guarantee: Because every source starts at distance 0 and BFS explores level-by-level, the first time any vertex $v$ is reached, it is guaranteed to be reached via the closest source.

Worked Example & SVGs

Consider the classic Rotten Oranges problem on a $3 \times 3$ grid:

• Grid values: 2 = Rotten (Source), 1 = Fresh, 0 = Empty.
• Initial state: [ [2, 1, 1], [1, 1, 0], [0, 1, 2] ] with sources at $(0, 0)$ and $(2, 2)$.

Mathematical Formulation

Let $G = (V, E)$ be an unweighted graph, and let $S \subseteq V$ be the non-empty set of source vertices. The distance to the nearest source $\text{dist}(v, S)$ for any vertex $v \in V$ is defined as:

where $d(s, v)$ denotes the standard unweighted shortest path distance (number of edges) from $s$ to $v$. Multi-source BFS guarantees that when a vertex $v$ is popped from the queue, its assigned distance equals $\text{dist}(v, S)$.

Complexity Analysis

Let $V$ be the number of vertices and $E$ be the number of edges:

Notice that the number of source vertices $k = |S|$ does not affect the asymptotic time complexity! Running $k$ independent single-source BFS passes would require $O(k \cdot (V + E))$ time, whereas multi-source BFS performs the exact same computation in a single linear pass.

Implementation

Below are production-ready multi-source BFS implementations in Python, C++, and Java:

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

Limitations