skip to content

Floyd-Warshall builds your travel-time matrix nightly, but aisles close mid-shift — recompute or patch?

level: principalimportance: nice to knowfreq 22%

answer

  1. The two directions of change are not symmetric
  2. Good news is cheap to absorb
  3. What did the matrix throw away — the runners-up
  4. One extra sweep through the changed endpoints
  5. Ask how wrong, for how long, seen by whom

basics

~20 s

Decide by direction of change. A cheaper edge patches in O(V^2); a closed aisle makes routes more expensive, has no cheap patch, and forces a rerun. Serve stale distances only where the error is bounded and visible.

solid answer

~50 s

Split the problem by the direction of the weight change, because the two directions are not symmetric. A **decrease** — a new shortcut, an aisle reopening — is patchable in O(V^2): for every pair, test whether routing through that edge's endpoints beats the stored value. An **increase or removal** is the hard case: paths that relied on the vanished edge must be replaced by alternatives the matrix never stored, and there is no cheap general repair, so you rerun. Keep the nightly full build as the baseline, apply cheap patches for improvements, and for closures choose between an immediate rerun, a scheduled one with an explicit staleness window, or distances that only ever over-estimate. Which you pick is a business call about how wrong a route may be for how long — and it must be visible to the operations team, not a silent drift.

code

pseudocode · 9 lines
pseudocode
// D already holds all-pairs distances; edge (u, v) drops to weight w
if w < D[u][v]
    D[u][v] = w
    for i in 0..n-1
        for j in 0..n-1
            if D[i][u] + w + D[v][j] < D[i][j]
                D[i][j] = D[i][u] + w + D[v][j]
// every improved route must use the cheapened edge, so one pass suffices
// an INCREASE admits no such patch: the replacement routes were never stored

go deeper

for a junior

Understand that a precomputed distance matrix is only correct for the graph it was built from, and that any change to the graph makes it stale. Knowing that the full rebuild is the safe fallback is enough here.

for a middle

Be able to explain the O(V^2) patch for a cheapened edge and why the same trick fails for a removed one — the matrix stores optima, not the alternatives a removal would need. That asymmetry is the technical core of the question.

for a senior

Weigh rerun against patch against staleness with real numbers for the vertex count in front of you, and say which failure direction a stale matrix produces. Bring up version-stamping the published matrix so staleness is observable rather than inferred.

for a principal

Own the policy, not just the mechanism: how stale may a routing answer be, who is alerted when the window is exceeded, and whether a cleverer dynamic structure is worth the maintenance burden it puts on the team that will debug it at 3am.

## Why this is a decision and not a lookup A precomputed all-pairs matrix converts a hard graph question into a flat array read, and that is exactly why it becomes a liability the moment the graph moves. The matrix is a cache of a `V^3` computation, and every cache raises the same three questions: how wrong may it be, for how long, and who finds out. On a fulfillment floor the graph really does move — an aisle closes for a spill, a lift goes down, a temporary conveyor opens — so the question arrives whether or not the design anticipated it. ## The asymmetry that structures the answer The two directions of change cost wildly different amounts to absorb. **An edge gets cheaper.** Suppose the directed edge `(u, v)` drops to weight `w`. Any pair whose distance improves must have its new best route pass through that edge, and the two halves on either side are unchanged distances already in the matrix. So one sweep over all pairs, testing `D[i][u] + w + D[v][j]` against `D[i][j]`, restores correctness in O(V^2) — a thousandth of a full rerun at V = 400, microseconds of work. Inserting a **new vertex** with known edges is the same order for the same reason. **An edge gets more expensive, or disappears.** Now every stored distance that happened to route through it is potentially wrong, and the replacement is a route the matrix never recorded — the whole point of a distance matrix is that it keeps optima, not the runners-up. There is no general cheap repair. Dedicated dynamic all-pairs structures exist and beat a full rebuild amortised, but they are substantially more machinery than a triple loop and are a real maintenance commitment for a team that will read this code once a year. For most floors the honest answer is: rerun. That asymmetry is the load-bearing fact of the whole design. Improvements are nearly free to absorb; degradations are not. ## The options on the table 1. **Rerun immediately on any closure.** Simplest to reason about and always correct. At V = 400 a rerun is a fraction of a second, so this is very often the right answer and the one to argue for first. The cost is not compute but coordination: something must publish a new matrix atomically while routing continues. 2. **Patch improvements, rerun degradations.** The O(V^2) patch keeps the common good news instant and reserves the expensive path for closures. Adds a code path that must be tested against a full rebuild, which is the real price. 3. **Serve stale, bounded distances.** Keep routing on last night's matrix and accept that closures make real travel times longer than reported. Viable only if you can bound the error and the consequence — a picker walking a slightly worse route is recoverable; a promise-time commitment computed from a fantasy distance is not. 4. **Coarsen and shrink the rerun.** Zone the floor, keep a small inter-zone matrix, and resolve within-zone routing locally. A closure then invalidates one zone plus the inter-zone layer. This buys cheap invalidation at the cost of slightly worse routes and a more complicated model. ## Choosing between them The deciding questions are organisational, not algorithmic. **How large can `V` get?** — at 400 the rerun is free and option 1 wins on simplicity alone; at 5,000 the rerun is minutes and staleness becomes a genuine trade. **What does a wrong distance cost?** — an under-estimate that promises a delivery is a different failure from an over-estimate that merely wastes steps, and note that stale-after-closure errors are always under-estimates, the dangerous direction. **How often does the graph change?** — a floor that changes twice a shift and one that changes twice a minute want different designs. **Who maintains it?** — a bespoke dynamic structure that one person understands is a worse system than a rerun anyone can debug at 3am, even when it is asymptotically better. ## What to build regardless of the choice Stamp every published matrix with the graph version it was built from, and make routing responses carry that stamp. Then staleness is observable rather than inferred, a bad route can be traced to the matrix that produced it, and the decision to serve stale data becomes an explicit, monitorable policy with an alert when the window is exceeded. That instrumentation matters more than which of the four options you pick — it is what turns a silent correctness risk into an operational one somebody owns. ## The answer to give Name the asymmetry first, since it is the insight; give the O(V^2) patch for improvements; say plainly that closures force a rerun and that at this vertex count a rerun is cheap enough to be the default; then move the conversation to staleness tolerance and versioning, because that is where the real risk lives. A candidate who reaches for a sophisticated dynamic structure without asking how big `V` is and how often the floor changes has answered a harder question than the one that was asked.

  • Why is a cheaper edge patchable in O(V^2) but a closed one not?
    Any route improved by a cheapened edge must pass through it, and the two halves either side are distances the matrix already holds — so one sweep over all pairs finds every improvement. A closure invalidates routes that used the edge, and their replacements are the second-best routes, which the matrix deliberately never stored. Recovering them means recomputing, not looking up.
  • If you serve last night's matrix after an aisle closes, in which direction are the errors?
    Always under-estimates: reported travel times are cheaper than reality, because the stored routes may use an aisle that no longer exists. That is the dangerous direction — it inflates throughput forecasts and can turn into promises the floor cannot keep. Over-estimating stale data merely wastes effort, so if you must serve stale distances, prefer a policy that errs upward.
  • When would you not keep a precomputed matrix at all for this floor?
    When the graph changes faster than a rebuild completes, or when the vertex count pushes the matrix past what you can hold and republish comfortably. At that point compute distances per query from the live graph and cache hot sources with short expiries, accepting a variable per-query cost in exchange for never serving a route built on a floor plan that no longer exists.

saying these in an interview costs you the question

  • Treats an edge increase and a decrease as equally patchable
  • Reaches for a dynamic structure without asking how big V is
  • Assumes a full rerun is always too expensive
  • Serves stale distances with no version stamp or alert
  • Ignores that staleness after a closure under-estimates cost

context

resolving links…