Why is one multi-source BFS better than k separate runs from k warehouse loading docks?

## The setup A warehouse floor is a grid of cells; some are shelving and impassable, the rest are walkable and connect to their walkable neighbours. Several cells are loading docks. You want, for every walkable cell, the number of moves to the **nearest** dock — the input to a picking-route heuristic, say, or a heat map of how badly served each aisle is. The reflex answer is: run BFS from each dock, keep k distance fields, then take the per-cell minimum. It is correct. It is also k times more work than necessary, and the argument for why is worth being able to make cleanly, because "seed them all at once" sounds like a trick until you can say why it is not. ## The virtual super-source Imagine adding one extra node joined to every dock by an edge of cost zero, and running an ordinary single-source BFS from it. Distance from that node to any cell is, by construction, the minimum over docks of the distance from that dock. Seeding the frontier with all k docks at distance 0 is precisely that traversal with the first expansion already done — the imaginary node's only job was to push the docks in. That reframing is the whole answer, because it means **no new correctness argument is needed**. Everything BFS already guaranteed applies unchanged. ## Why the queue discipline survives The usual proof rests on the frontier being non-decreasing in distance, and that property came from all entries starting equal and every edge advancing the count by one. Both still hold: all k seeds sit at distance 0, so the frontier contains only distances `d` and `d+1` at any moment, exactly as before. A cell's first discovery is therefore its minimum distance over the whole seed set. This is also where the technique's precondition lives. **All seeds must start at the same distance.** If one dock were given a head start — say it is "already 3 moves of overhead away" — the frontier would no longer be sorted, first arrival would stop being final, and the technique silently returns wrong numbers. That is not a plain-BFS problem any more; it needs a discipline that can order unequal starting costs. ## The cost comparison, stated for a skeptic - **k separate runs:** O(k(V + E)) time, plus a fold over k distance fields to take the minimum — another O(kV) — and either O(kV) memory to hold them all or the bookkeeping to fold incrementally. - **One multi-source run:** O(V + E) time, O(V) memory, no fold. Each cell is discovered once, full stop. On a 1000 × 1000 floor with 20 docks that is 20 million cell visits against one million. The reviewer's usual objection — "but the frontier starts bigger" — is answered by noting that the frontier is still bounded by the widest layer and each cell still enters it exactly once; a bigger seed set makes the traversal *shallower*, not heavier. ## What the single pass will not tell you This is the caveat that separates a memorised trick from understanding. The multi-source run computes distance to the nearest seed and *loses which seed it was*, unless you deliberately carry that information. Two consequences: - **If you need the owning dock**, propagate an owner label alongside the distance: a seed owns itself, and a cell discovered from `u` inherits `u`'s owner. That yields a nearest-dock partition of the floor, with ties broken by seeding and neighbour order rather than by any principle — so if ties must be broken deterministically, say by dock id, you have to say so explicitly. - **If a caller needs the distance from one *particular* dock**, the multi-source result cannot answer it, and that dock needs its own single-source run. A request like "how far is every cell from dock 7 specifically, so we can plan its closure" is a different question, and answering it from the nearest-dock field is a real and easy mistake. ## When k separate runs are still the right call Judgment, not dogma. If k is 2 and the floor is small, two runs are simpler to read, trivially parallel, and cheap enough that nobody will ever notice. If the per-dock fields are themselves the product — a dashboard showing each dock's reach — you need them anyway. The multi-source win is real and grows linearly in k, but the decision to take it should follow from what the caller actually consumes. ## Saying it out loud "Seeding every dock at distance zero is the same traversal as a single source joined to all of them by zero-cost edges, so the ordering argument is unchanged and the first time I touch a cell I have its distance to the nearest dock. It is one linear pass instead of k, with no fold at the end. What it does not give me is per-dock distances — if you need those, that is a different query and it costs what it costs."