Multi-source BFS

Multi-source BFS finds, for every vertex of a graph or every cell of a grid, the fewest edges to the nearest of several sources, such as the nearest exit or the nearest burning cell. It is one breadth-first search whose queue (first in, first out) starts with all of them. If the edges have different lengths, use Dijkstra's algorithm with all sources at distance 0 instead.

Explanation

A corridor of 5 rooms in a row has a street door at each end, in rooms 1 and 5. We call a room with a street door an exit. During a fire drill, everyone leaves through the nearer exit. How many doors between rooms does each person pass? Rooms 1 and 5 need 0, because they are exits. Rooms 2 and 4 are next to them and need 1. Room 3 is in the middle and needs 2 either way. Picture two waves that start at both ends at the same moment and meet in room 3.

Fig. 1. Rooms with the same number light up in the same frame. The number next to a room counts its doors to the nearer exit.

Real floors are not one corridor. On this floor 8 rooms are joined by 8 doors, and rooms 1 and 8 are exits.

Fig. 2. Find the fewest doors from every room to an exit. Watch room 7.

Here the nearer exit can't be seen at a glance. Room 3 is 2 doors from either exit. Room 7 is 1 door from exit 8 but 3 doors from exit 1.

A breadth-first search gets this right: run one search from exit 1, then one from exit 8, and keep the smaller number for each room. For rooms 1 to 8, exit 1 alone gives 0 1 2 5 1 2 3 4, exit 8 alone gives 4 3 2 1 3 2 1 0, and the smaller of each pair is 0 1 2 1 1 2 1 0. But each search goes through every room again. A grid of 1000 × 1000 cells with 1000 exits would take 10^9 steps.

The second search mostly repeats the first, so try letting it skip rooms that already have a number. Run exit 1's search first. Then give exit 8 a 0 and let its search spread, but only into rooms without a number. Room 7 already has 3 from exit 1's search, along the red route. So exit 8's search does not enter room 7, and room 7 keeps 3, though the blue route to exit 8 has 1 door. Even room 4, whose only door leads to exit 8, keeps 5.

Fig. 3. The numbers after exit 1's search and then exit 8's search.

Exit 1's search reached room 7 first only because it started first. So start both searches at the same moment, like the two waves in the corridor: first every room 1 door from any exit, then every room 2 doors from any exit, and so on. Then the first wave to reach a room comes from its nearest exit. A later wave can only bring the same number or a larger one, so skipping rooms that already have a number is now right. In practice, both exits go into the queue with 0 before the search starts, and nothing else changes.

This is multi-source BFS. A source is a vertex the distances are counted from; here the sources are the two exits. As in BFS, a room is reached when it gets its number and joins the queue, and taken when it leaves the queue.

Rooms 1 and 8 are exits: both get 0 and join the queue, room 1 first.

Room 1 is taken from the front of the queue.

Room 2 is reached from room 1 and gets 0 + 1 = 1. It joins the back of the queue.

Room 5 is reached from room 1 and gets 0 + 1 = 1. It joins the back of the queue.

Room 8 is taken from the front of the queue.

Room 7 is reached from room 8 and gets 0 + 1 = 1. It joins the back of the queue.

Room 4 is reached from room 8 and gets 0 + 1 = 1. It joins the back of the queue.

Room 2 is taken from the front of the queue.

Room 1 was already reached, so it keeps 0.

Room 3 is reached from room 2 and gets 1 + 1 = 2. It joins the back of the queue.

Room 5 is taken from the front of the queue.

Room 1 was already reached, so it keeps 0.

Room 6 is reached from room 5 and gets 1 + 1 = 2. It joins the back of the queue.

Room 7 is taken from the front of the queue.

Room 6 was already reached, so it keeps 2.

Room 3 was already reached, so it keeps 2.

Room 8 was already reached, so it keeps 0.

Room 4 is taken from the front of the queue.

Room 8 was already reached, so it keeps 0.

Room 3 is taken from the front of the queue.

Room 2 was already reached, so it keeps 1.

Room 7 was already reached, so it keeps 1.

Room 6 is taken from the front of the queue.

Room 5 was already reached, so it keeps 1.

Room 7 was already reached, so it keeps 1.

The queue is empty. Rooms 1 to 8 have 0 1 2 1 1 2 1 0.

1/26

Fig. 4. Step through multi-source BFS on the floor. Green rooms are taken, light blue rooms are reached and wait in the queue, shown below the map. A grey arrow points to a room that was already reached.

Compare room 7: it now has 1, not the 3 it got in Fig. 3.

Fire on a grid

A field has some stones, which don't burn. The fire starts in two cells at the same moment, and each minute it spreads from every burning cell to its side neighbours. The minute each cell catches fire comes from the same wave, with both burning cells in the queue at minute 0. In Fig. 5 the fire starts in the top-left and bottom-right corners.

Fig. 5. Two fires spread together, one minute per frame, up to minute 3.

Implementation

In code, rooms are vertices, doors are edges, and the exits are the sources. Let's keep the numbers from above in an array d, the distances: d[v] is the fewest edges from v to the nearest source, and d[v] == -1 while v is not reached.

1. Initialise: d[v] = -1 for every vertex. For every source s, set d[s] = 0 and push s.

2. Take the next vertex v from the front of the queue.

3. Expand its edges: look at each neighbour u of v.

4. Mark it: if d[u] == -1, then u is reached now: set d[u] = d[v] + 1 and push u to the back of the queue.

5. Stop when the queue is empty; otherwise repeat from step 2.

The program reads n and m, then m lines u v: a two-way edge between u and v. Vertices are numbered from 1 to n. Then come k, the number of sources, and the k sources. The program prints d[1] to d[n], with -1 for a vertex no source can reach. On a second line it prints from[1] to from[n], the source the search reached each vertex from. For the floor from Fig. 2 the input is:

8 8
1 2
2 3
1 5
5 6
6 7
3 7
7 8
4 8
2
1 8

The graph is stored as an adjacency list, where adj[v] lists the neighbours of v. A source listed twice is pushed only once, because the second time it already has 0.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);   // remove this line if the edges are one-way: they are then stored reversed
        adj[v].push_back(u);
    }

    int k;
    cin >> k;
    vector<int> d(n + 1, -1);
    vector<int> from(n + 1, 0);   // only needed to know the nearest source
    queue<int> q;

    // initialise: every source gets 0 and joins the queue
    for (int i = 0; i < k; i++) {
        int s;
        cin >> s;
        if (d[s] == -1) {
            d[s] = 0;
            from[s] = s;   // only needed to know the nearest source
            q.push(s);
        }
    }

    while (!q.empty()) {          // stop: when the queue is empty
        // take the next vertex
        int v = q.front();
        q.pop();

        // expand its edges
        for (int u : adj[v]) {
            if (d[u] == -1) {
                // mark it
                d[u] = d[v] + 1;
                from[u] = from[v];   // only needed to know the nearest source
                q.push(u);
            }
        }
    }

    for (int v = 1; v <= n; v++) {
        cout << d[v] << (v < n ? ' ' : '\n');
    }

    // print the nearest source of every vertex; remove this block if you only need distances
    for (int v = 1; v <= n; v++) {
        cout << from[v] << (v < n ? ' ' : '\n');
    }
}

Each vertex is pushed and taken at most once, however many sources there are, and each edge is checked twice, once from each end. So the search takes O(n + m) time and memory, against O(k(n + m)) for one search per source.

Which source is nearest

Each vertex can also remember which source the search reached it from: it takes the source of the vertex that reached it. That is the array from in the program: a source gets itself, a vertex u reached from v gets from[v], and from[u] stays 0 if no source reaches u. On the floor from Fig. 2 the second line is 1 1 1 8 1 1 8 8 for rooms 1 to 8.

Fig. 6. Each room has the colour of the exit the search reached it from. Thick edges show which room reached which.

Multi-source BFS on a grid

On a grid, each open cell is a vertex, and two open side neighbours are joined by an edge. Here is the field from Fig. 5, with # for stones and F for the cells where the fire starts:

F . . # .
. # . . .
. # . # #
. . . # .
# # . . F

The loop is the same as in BFS on a grid, with the four moves dr, dc and the check that a cell is inside the grid. The initialise step pushes every F with 0. Here g holds the rows as strings, and the grid has R rows and C columns:

// initialise: every burning cell gets 0 and joins the queue
vector<vector<int>> d(R, vector<int>(C, -1));
queue<pair<int, int>> q;
for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
        if (g[r][c] == 'F') {
            d[r][c] = 0;
            q.push({r, c});
        }

The search takes $O(RC)$ time and memory. If every grass cell is reached, the minute when the whole field is burning is the largest d[r][c]. If some grass cell still has -1, stones cut it off, and the field never burns completely.

One-way edges

With one-way edges, a search that follows the arrows from the sources finds the fewest edges from the nearest source. Often the question is the opposite: the fewest edges from each vertex to an exit. Then store each edge reversed: remove the line adj[u].push_back(v);, so an edge from u to v is kept only as adj[v].push_back(u);. A search from the sources along the reversed edges walks every route backwards, so d[v] becomes the fewest edges from v to a source. For example, take rooms 1, 2 and 3 with one-way doors from 1 to 2 and from 2 to 3, and the exit in room 3. Following the arrows from room 3 reaches nothing and gives the distances -1 -1 0. With the edges stored reversed the program gives 2 1 0.

Correctness proof

Imagine one more vertex, the street (usually called a virtual source), joined by an edge to every source. Run a plain BFS from the street. It takes the street first and pushes every source with distance 1, in the order of the list. From then on it runs exactly like multi-source BFS, and every distance is 1 larger.

Fig. 7. The imagined street s and its two edges, with the distances of a BFS from s.

BFS from one source is correct, so the street search gives each vertex $v$ the fewest edges from the street to $v$. Every route from the street starts with the edge to some source. So the fewest edges from the street to $v$ is 1 plus the fewest edges from $v$ to its nearest source. Multi-source BFS gives $v$ exactly 1 less, which is the answer.

When doors have different lengths

The proof counts doors, not metres. Suppose the door between rooms 7 and 8 leads through a 5-metre corridor and every other door joins rooms 1 metre apart. BFS gives room 7 the distance 1, from exit 8. Its shortest route is 3 metres, through rooms 3, 2 and 1 to exit 1. Dijkstra's algorithm with both exits at 0 gives 3.

Common mistakes

• Running a separate BFS from each source, which takes O(k(n + m)) and is far too slow when there are many sources. Put all sources in one queue instead.

• Running the sources one after another with one shared d (Fig. 3), so a vertex keeps the number from the source that ran first, not from the nearest. Push all sources before the loop starts.

• Pushing every source but setting d[s] = 0 only for the first one, so the other sources keep $-1$ and give their neighbours wrong distances. Set d[s] = 0 for every source at its push.

• Taking the largest d[r][c] as the minute the whole field burns without checking for $-1$: stones can cut some grass cells off, and then the field never burns completely. Check every grass cell for $-1$ first.

• Expecting the run to give the distance to every source, when it gives only the nearest one. When a problem needs the distance to each of two sources, for example to add or compare them, run a separate BFS from each.

Similar algorithms

Connected components also start many searches, but one after another, each claiming a whole component.

Dijkstra's algorithm is for doors of different lengths, as with the 5-metre corridor above. Its queue also starts with every source at distance 0.

Practice