Multi-Source BFS
Graphs: lesson 15 of 16
Seed the queue with every source and one sweep answers them all.
Lesson 15 of 16 · 5 min
Multi-Source BFS
Step 1 of 7
Two exits, nine tiles. Running a separate search from each exit would walk the floor twice for no reason.
The Idea
Running BFS once per source repeats the same work S times. Instead, push every source into the queue with distance zero and let a single wavefront expand. Whichever source reaches a node first is its nearest one, which is exactly the answer. One sweep, one queue, O(V + E) total.
Real-World Example
A warehouse floor plan asking how far the furthest worker stands from an exit. Every exit is a source. One flood outward labels each tile with its walk to the closest exit, and the largest label is the number the fire inspector wants.
The Code
from collections import deque
grid = [["hot", "cool", "cool"],
["cool", "cool", "hot"],
["cool", "cool", "cool"]]
rows, cols = len(grid), len(grid[0])
dist = [[-1] * cols for _ in range(rows)]
q = deque()
for r in range(rows):
for c in range(cols):
if grid[r][c] == "hot": # every source starts at 0
dist[r][c] = 0
q.append((r, c))
while q:
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
print(max(max(row) for row in dist)) # 2Your turn
What does this print?
from collections import deque
d = [[-1, -1, -1], [-1, -1, -1]]
q = deque([(0, 0), (1, 2)])
d[0][0] = d[1][2] = 0
while q:
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < 2 and 0 <= nc < 3 and d[nr][nc] == -1:
d[nr][nc] = d[r][c] + 1
q.append((nr, nc))
print(d[0][2], d[1][0])Mini quiz
1 / 3