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'.