Multi-source BFS

March 2026 · 15 min read

Standard BFS starts from one source. Multi-source BFS starts from multiple sources simultaneously. All sources are enqueued at the start (level 0), and the BFS radiates outward from all of them at once. This technique solves a whole class of "nearest distance" and "spreading" problems elegantly.

The Idea

Instead of one source, enqueue all sources before the BFS loop begins. The BFS then finds the shortest distance from any source to every other node, all in one pass.

// Multi-source BFS
queue<int> q;
vector<int> dist(n, -1);

// Enqueue ALL sources
for (int src : sources) {
    dist[src] = 0;
    q.push(src);
}

// Standard BFS from here
while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (int neighbor : adj[node]) {
        if (dist[neighbor] == -1) {
            dist[neighbor] = dist[node] + 1;
            q.push(neighbor);
        }
    }
}
// dist[i] = shortest distance from i to nearest source

This is identical to standard BFS except the initialization. You can think of it as adding a virtual "super source" connected to all real sources with 0-weight edges.

Classic: Rotten Oranges

Problem: Given a grid where each cell is empty (0), fresh orange (1), or rotten orange (2). Every minute, fresh oranges adjacent to rotten ones become rotten. Find the minimum time for all oranges to rot, or return -1 if impossible.

This is multi-source BFS on a grid. All initially rotten oranges are sources (level 0). Each BFS level represents one minute of spreading.

Initial State

Two rotten oranges at (0,0) and (2,2). Both go into the queue at time 0.

Implementation

int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    int fresh = 0;

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.push({i, j});
            else if (grid[i][j] == 1) fresh++;
        }

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    int minutes = 0;

    while (!q.empty() && fresh > 0) {
        int sz = q.size();
        for (int k = 0; k < sz; k++) {
            auto [r, c] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nr = r + dx[d], nc = c + dy[d];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n
                    && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    q.push({nr, nc});
                    fresh--;
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

Pattern: Nearest Distance to Target

Any problem asking "for each cell, what is the distance to the nearest X?" is multi-source BFS with all X-cells as sources.

Example: 01 Matrix. Given a binary matrix, find the distance of every cell to the nearest 0.

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    queue<pair<int,int>> q;

    // All 0-cells are sources
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (mat[i][j] == 0) {
                dist[i][j] = 0;
                q.push({i, j});
            }

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n
                && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return dist;
}

0-1 BFS

A variation for graphs where edge weights are either 0 or 1. Instead of a regular queue, use a deque. Push 0-weight neighbors to the front, 1-weight neighbors to the back. This maintains the BFS invariant (process nodes in non-decreasing distance order) without needing Dijkstra.

vector<int> bfs01(int source, vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;

    dist[source] = 0;
    dq.push_front(source);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    return dist;
}

Time complexity: O(V + E), same as regular BFS. Much faster than Dijkstra's O((V + E) log V) for this special case.

More Multi-source BFS Problems

Complexity

• Time: O(V + E) or O(m * n) for grids. Same as single-source BFS.
• Space: O(V) or O(m * n). Queue can hold all sources initially.