Algorithm
int[] multiSourceBfs(int[] sources, List[] graph) {
int[] dist = new int[graph.length];
Arrays.fill(dist, Integer.MAX_VALUE);
Deque q = new ArrayDeque<>();
for (int s : sources) { dist[s] = 0; q.offer(s); }
while (!q.isEmpty()) {
int u = q.poll();
for (int v : graph[u]) if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
q.offer(v);
}
}
return dist;
} Advertisement
Applications
'Distance to nearest gate' problems. Wildfire simulation (fire from multiple points). Voronoi diagrams on grids.
Advertisement
Complexity
Same as BFS: O(V+E). Number of sources doesn't matter.
vs N BFS runs
N BFS: O(N × (V+E)). Multi-source: O(V+E). Huge win for computing 'nearest of many'.