Many starts at once
Sometimes you want the distance from each vertex to the nearest of several sources, not just one. Examples include the closest fire station, the nearest infected cell, or the distance to the nearest gate. Multi source BFS answers all of these in a single sweep.
Seed the queue with all sources
Ordinary BFS starts with one vertex in the queue. Multi source BFS simply starts with all source vertices in the queue at once, each at distance zero.
- Push every source into the queue and mark them visited at distance zero.
- Run BFS normally, expanding the queue layer by layer.
- The first time any vertex is reached, the distance recorded is its distance to the nearest source.
Because all sources expand together at the same pace, the rings from different sources meet exactly at the midpoints, and every vertex is claimed by whichever source reaches it first.
Why it works in one pass
This is equivalent to adding an imaginary super source connected to all real sources with zero weight, then running one BFS. It avoids the slow alternative of running a separate BFS from every source and taking the minimum.
Key idea
Seed the BFS queue with every source at distance zero so one sweep yields each vertex's distance to its nearest source.