How long a reweighting stays true

One Bellman–Ford buys every Dijkstra priced three ways of computing all-pairs shortest paths on a graph with negative arcs, and found Johnson’s method cheapest over a wide band of densities. Its reweighting — one Bellman–Ford run from a virtual source joined to every vertex at cost zero, whose distances become a potential that makes every arc’s repriced cost non-negative — came to under one per cent of the total, because it is paid once and then divided over 256 Dijkstra runs.

A system answering queries as they arrive divides it over nothing. The first query pays for the whole preparation and gets one shortest-path tree for it; the second query gets the preparation free. So the question that essay left is a break-even: how many single-source queries have to arrive before paying in advance is cheaper than not.

This page answers it, and the answer is smaller than expected — which makes the interesting question the second one. A potential is a statement about the arcs as they were. This page measures how long that statement stays true.

Two queries and a bit #

The setting is the one the all-pairs page used: a directed graph of 256 vertices whose arcs cost one to nine plus the difference of a fixed random potential, so that a third of them are negative and no cycle is. Queries name a source; the answer is that source’s distances to every vertex, and every answer is compared entry by entry against the other method’s.

The preparation is repaid before the third query. That is not a surprising number once it is stated the right way round: the reweighting is one Bellman–Ford run, so it costs about what one query would have cost, and it has to be repaid out of the saving on each later query. The saving is 32% — Dijkstra on repriced arcs costs 8,069 against Bellman–Ford’s 11,787 — so about three queries’ worth of saving covers one query’s worth of preparation.

The contrast between that plate and the one above it is the whole of the reframing. Divided over 128 sources the preparation is a rounding error and the only question is which method is asymptotically better. Divided over one source it is a whole query, and the question becomes when the second query arrives — which, as the next plate shows, is almost immediately, so the framing that put the preparation at the centre was answering a question nobody has.

Both halves of that arithmetic are worth attention. The preparation is cheap because Bellman–Ford from a virtual source joined to everything converges in very few passes: every vertex is at distance at most zero immediately, so the pass count is set by the longest chain of improvements rather than by the diameter. The saving per query is only 32% because Bellman–Ford on this graph is not paying its worst case either — its early exit stops it after a handful of passes, so the classical factor of $V$ between the two methods does not appear.

The break-even does not move much with density #

A break-even of three queries would be a different kind of finding if it were three at one density and three hundred at another.

It does not move much. Across a factor of thirty-two in density the break-even stays between one and four queries, and it is not monotone — the sparse end is cheapest because Bellman–Ford’s early exit fires latest there, and the dense end is cheap because Dijkstra’s advantage is largest there. Nothing on that plate would change a design decision. A system that expects more than about five queries in the lifetime of its graph should store the potential, at any density drawn.

That makes the query count the wrong parameter, and it is worth saying why explicitly. The all-pairs page’s framing — preparation divided over many uses — suggests a trade that becomes better the more uses there are, and it is one; but the preparation here is a single run of the same algorithm the queries would otherwise use, so it can never be more than a few queries’ worth. Preparation that dominates is preparation that computes something the queries could not, and the structure paid for before the first query is about the case where it does. Johnson’s reweighting is not that case.

What is actually at stake: the graph moving #

A potential is valid for a set of arc costs. If an arc’s cost falls, its repriced cost can go negative, and Dijkstra on repriced arcs stops being correct — not slightly wrong, but wrong in the way the adversary who hides the edge describes, settling a vertex before the route that would have improved it is found.

So the measurement that matters is not how many queries arrive but how much changes between them. Here a stated share of arcs have their costs redrawn between queries, from the same construction — one to nine plus the fixed potential’s difference — so no cycle can go negative and the question stays answerable. Before each query the stored potential is checked against every arc, and recomputed if any repriced cost is negative.

Half a per cent of arcs is ten arcs out of two thousand. That is the whole margin: a graph in which ten arc costs change between one query and the next is a graph on which the reweighting is worth nothing, and one in which forty change is a graph on which storing it costs 43% more than not bothering.

The shape of that curve is not the usual diminishing one. It rises through one and keeps rising, because a potential that is recomputed on most queries is paying for a Bellman–Ford run and a Dijkstra run per query where the simple method pays for one Bellman–Ford. Past the crossing the stored potential is not merely useless; it is the more expensive method by construction, and its cost tends to the sum of both rather than to either.

A potential’s life, and the rate that sets it #

The recomputation count is a consequence of something simpler, which can be measured on its own: how likely one arc’s redraw is to break the potential.

The per-arc rate is the quantity with an explanation. For each arc, counting how many of its nine possible redrawn costs would leave it negative under the potential in force gives 6.3% to 7.0% across every churn rate measured — the same number whether one arc moves or forty. It is a property of how tight the potential is against these arcs, not of the update process, and once it is known the rest follows: an update touching $k$ arcs breaks the potential with probability $1 - (1-q)^k$, and the number of queries between recomputations is geometric with that parameter.

The account is right where several arcs move at once — 3.42 against a predicted 3.18 at four arcs, 1.16 against 1.06 at ten, 0.07 against 0.08 at forty — and it understates the potential’s life by about a third when one arc moves, predicting 13.5 where 19.9 is measured. The likeliest reason is an assumption the account makes and the process does not honour: it treats every redraw as independent of every other, while an arc redrawn twice between recomputations has its second redraw measured against a cost the potential has already survived. At forty arcs an update that hardly matters, because almost every update breaks the potential anyway; at one arc an update, over a life of twenty queries, twenty of the two thousand arcs have moved and a repeat is not rare. The account is reported as it stands rather than fitted, because a fitted constant would hide exactly this.

Where the 6.6% comes from #

The rate is not a fitted constant. It can be read off the potential’s own slack.

A redraw replaces an arc’s raw cost, one to nine, with another drawn the same way, and the repriced cost moves by exactly the difference. So an arc currently costing $c$ with slack $s$ is broken by any of the redraws below $c - s$, which is $c - s - 1$ of the nine when that is positive and none of them otherwise. Averaging that over the arcs gives the 6.6% the survival plate uses, and the two largest contributions are visible in the histogram: the 277 arcs at zero slack, which lose on any fall — about four of nine redraws on average — and the 120 at slack one, which lose on about three.

That is also why the rate is a property of the graph rather than of the traffic. The 277 arcs at zero slack are not an accident of this construction; a potential computed by Bellman–Ford from a virtual source is tight, meaning every vertex’s value is achieved by some path, and the arcs on those paths necessarily reprice to zero. There are at least $V - 1$ of them on any connected graph, so a reweighting’s fragility has a floor: at least one arc in every $V$ is broken by any fall at all, whatever the costs.

Whether an update has to be believed #

There is a cheaper policy hiding in the check. The potential is recomputed when some repriced arc is negative, and the check that discovers this is a pass over every arc — which costs about a fifth of a Bellman–Ford pass and is already counted above. But an update that raises an arc’s cost cannot break anything, since raising $w$ raises $w + h(u) - h(v)$. Only a fall can, and only a fall past the arc’s current slack.

That gives a system a test it can apply per update rather than per query: when an arc’s cost changes, compare the new repriced cost with zero, and mark the potential invalid only if it is negative. It is one subtraction against a full scan, and it is exactly the 6.6% event measured above. Nothing on this page prices the two checks against each other, because the scan is the cheaper part of the recomputation it guards; the point is that the rate the survival plate measures is the rate a real system would test at, arc by arc, and it can be known in advance.

What no policy avoids is the recomputation itself. A potential that has gone negative on one arc is not repairable by fixing that arc: the potential is a set of distances from a virtual source, and one arc’s fall can lower the distance to every vertex reachable through it. An estimate is a reweighting is the reason the two are the same object seen twice — a potential that makes arcs non-negative and an estimate that guides a search are one function with two uses — and it is why a local repair is not available in either use.

A preparation is not an investment until it survives #

The arithmetic of a preparation repaid over many uses is the arithmetic of amortisation, and what amortised means is the reason to be careful with it: a cost spread over a sequence of operations is a real saving only if the sequence happens. A dynamic array’s doubling is amortised over the appends that follow it and those appends are guaranteed, because nothing outside the structure can undo them.

A reweighting has no such guarantee. The sequence it is amortised over is the run of queries before the graph moves, and that run has a length the structure does not control. The churn plate is that length turned into money: at no churn the sequence is unbounded and the preparation is free; at half a per cent the sequence is one query long and the preparation is paid every time, which is the definition of not being a preparation at all.

The same shape appears wherever a structure is built in advance against a world that can change under it. Where the table starts paying priced a lookup table against recomputation and found the crossing in the number of lookups; a table over a changing domain has the crossing in how often the domain changes instead. The structure that was supposed to halve is the other failure of the same reasoning — a preparation whose stated benefit did not arrive — and this one is a preparation whose benefit arrives and then leaves.

What makes this case unusually clean is that the length of the sequence is measurable before the preparation is paid for. The per-arc break rate is a pass over the arcs; the number of arcs that move between queries is in the update log. Multiply the two and the expected run length falls out, and with the break-even at three queries the decision is a comparison of two numbers a system already has. The model a bound was quoted in is the general complaint that a bound is useless without the model it was stated under, and the model here is a static graph — stated nowhere in the description of Johnson’s method, because in the all-pairs setting there is no time for anything to change.

What the two numbers say together #

A designer holding both results has a rule with no free parameters in it.

If the graph is static, store the potential. It repays itself before the third query at every density measured, and thereafter every query costs 32% less. There is no query count small enough for this to be the wrong call except one and two.

If the graph changes, measure the per-arc break rate, not the query rate. It is computable from the arcs and the potential in one pass, it was 6.6% here, and it says how many arcs may move between queries before the stored potential is a loss: about ten, on this graph, which is half a per cent of them.

And the two questions are not the same question. A system answering a million queries on a graph that changes ten arcs between each of them should not store a potential, and a system answering five queries on a graph that never changes should. The parameter the all-pairs framing puts first — how many uses the preparation is divided over — turns out not to decide anything here, and the parameter it does not mention decides everything.

What is not measured here #

One graph family. Arcs cost one to nine plus the difference of a random potential on 256 vertices, which is the construction the all-pairs page used, and it is what makes the per-arc break rate 6.6%. A graph whose arc costs have a wider spread would have a looser potential and a lower rate; a graph whose shortest-path structure is nearly determined — a near-tree — would have a tighter one and a higher rate. The one part of the rate that does not depend on the family is the floor the tight arcs set, and it is the part with an argument rather than a measurement behind it.

Redraws of the same width. A redraw can move an arc’s cost by at most eight, so no single update can drive a repriced cost far below zero. An update model that halved a cost, or set it from a different distribution, would break more arcs and break them worse, and the recomputation would be no more expensive — which is the asymmetry that makes the repair proposed at the end of this page worth measuring.

Redraws from the original distribution. Every update replaces a cost with one drawn the same way, so the graph is statistically stationary and the potential’s rate does not drift. A system whose costs trend — congestion rising through a morning — faces a rate that changes while it is being measured.

No negative cycles, ever. The construction forbids them, so an update can never make the question unanswerable. A real dynamic graph can, and detecting it costs a Bellman–Ford run that the policies here would not otherwise pay for.

One recomputation policy. The potential is recomputed the moment it is invalid. A system could instead keep answering with Bellman–Ford until the next scheduled recomputation, trading a known worse per-query cost for a fixed preparation schedule; nothing here prices that.

The check itself is counted, the per-arc test is not. The scan over every arc is included in the stored method’s work above. The per-update subtraction the previous section describes is not, because no run here uses it.

Still open: a potential that is rebuilt from where it broke #

Every recomputation on this page starts again from the virtual source, which throws away a potential that was correct everywhere except behind one fallen arc. That is visibly more than is needed. When an arc $(u, v)$ falls so that $w + h(u) - h(v) < 0$, the only distances that can have fallen are those of vertices reachable from $v$, and the repair is the same relaxation Bellman–Ford does, started from $v$ with the deficit rather than from a virtual source with nothing.

The measurement that follows implements that repair, counts the arcs it has to relax against the full recomputation’s, and sweeps the churn: the prediction from this page is that at one arc an update the repaired region is a small fraction of the graph and the stored potential’s crossing moves well past half a per cent, and that as several arcs fall at once the repairs overlap until the repaired region is the whole graph and the two costs meet. Where that meeting falls, against the 6.6% per-arc rate, is the number that decides whether a routing system with negative costs can hold a potential at all.