Why precompute all pairs with Floyd-Warshall for 400 pick stations instead of 400 single-source runs?

## Framing the decision The wrong way to choose is to compare O(V^3) against O((V + E) log V) and declare the smaller symbol the winner — the two bounds answer different questions and the second must be multiplied by the number of sources you actually need. The right way asks three questions: how dense is the graph, how many distinct sources will be queried, and how large is `V`. ## Density On a fulfillment floor with 400 pick stations, the travel-time graph is close to complete: from any station you can reach most others, and the edge weight is a measured walk or conveyor time. Call it dense, `E ≈ V^2`. Put numbers on both sides at V = 400: | Approach | Work | Rough step count | Per-step cost | |---|---|---|---| | One all-pairs triple loop | V^3 | ~6.4e7 | one add, one compare | | A greedy search per source | V * (V + E) log V | ~5e8 | heap push/pop, pointer chasing | The asymptotic gap is a factor of `log V` in favour of the triple loop on a dense graph, but the constant-factor gap is larger still. The triple loop has no priority queue, no visited set, no adjacency traversal — it is arithmetic over a contiguous block of cells, which hardware handles about as well as it handles anything. The repeated-search approach pays queue maintenance on every relaxation. On a **sparse** graph the table inverts completely. With V = 20,000 and E = 60,000, repeated single-source searches cost about `2e4 * 8e4 * 14 ≈ 2e10` heap-flavoured steps — large but finite — while the triple loop asks for `8e12` steps and a 4e8-cell matrix. There, per-source search is the only option that runs at all, and you would compute distances lazily per query rather than materialising anything. ## Query pattern Density decides the cost of building the answer; the query pattern decides whether building it is worth anything. All-pairs precomputation is an amortisation bet: pay `V^3` once, then serve every future distance question as a single array read. That bet pays when routing decisions arrive continuously and from arbitrary stations — a picker finishing at one station and being assigned the next, a batching heuristic evaluating dozens of candidate orderings per second, a simulation sweeping every pair. It does not pay when queries come from three fixed depots, in which case three single-source runs cost a fraction of the matrix and you would be silly to build the rest. So the honest one-line rule is: **all-pairs precompute when the graph is small and dense and the query sources are unpredictable; per-source search when the graph is sparse or the sources are few.** ## The ceiling, and how to spot it early Both resources in this algorithm scale badly and they scale at different rates, so it is worth knowing where the wall is before you start. Ten times the vertices is a thousand times the work and a hundred times the memory. At V = 400 the matrix has 160,000 cells; at V = 10,000 it has 1e8 cells, which is already an uncomfortable allocation, and the run is 1e12 steps. At V = 100,000 the matrix alone would need 1e10 cells and the run 1e15 steps — the approach is not slow there, it is off the table, and no engineering effort inside the algorithm recovers it. The interesting part of that observation is that **memory usually fails first**: you can wait out a long batch job, but you cannot allocate a matrix that does not fit, and the O(V^2) output is unavoidable even in principle if you genuinely want every pairwise answer stored. That gives a cheap design test. Before choosing all-pairs precompute, write down the vertex count at the largest facility you expect to serve, cube it, and square it. If either number is uncomfortable, the answer is per-query search with caching of hot sources, or a coarsened graph — cluster stations into zones, precompute the small all-pairs matrix over zones, and resolve within-zone hops locally. ## What else the precompute buys A materialised matrix is not just fast; it is *predictable*. Every distance query costs the same, so downstream planners get a flat cost model and their own complexity analysis stops depending on graph shape. It is also trivially shareable and cacheable, and it makes the routing layer stateless. Those operational properties are often the real argument in a review, and they are worth saying out loud alongside the step counts. ## The trap to avoid Do not defend the choice with "the triple loop is asymptotically better", full stop. It is better *on dense graphs*, and it is worse — catastrophically so — on sparse ones. A candidate who names density and query pattern as the two axes, then puts numbers on both sides for the specific `V` in front of them, is doing the thing the question is actually testing.