A potential mended where it broke

One Bellman–Ford buys every Dijkstra measured Johnson’s trick. A graph with negative arcs needs Bellman–Ford, which is slow, but one Bellman–Ford run from a virtual source gives every vertex a potential $h$. Repriced by $w + h(u) - h(v)$, every arc becomes non-negative, and every query after that can use Dijkstra.

How long a reweighting stays true put that trick into a stream of queries on a graph that changes. On a 256-vertex graph with 2,009 arcs, the reweighting cost 10,045 relaxations and paid for itself after under three queries. When arc costs were redrawn between queries, the stored potential broke whenever some repriced arc went negative. Recomputed from scratch each time, it stopped paying at about half a per cent of arcs redrawn.

It ended by pointing out waste in its own method. A recomputation starts again from the virtual source and throws away a potential that is still correct everywhere except behind the arcs that fell. When an arc $(u, v)$ falls so that its repriced cost is negative, the only values that can need to fall are those of vertices reachable from $v$. The repair is the same relaxation Bellman–Ford performs, started at the damage and not at the source. The prediction was that single-arc repairs would be small, and that as more arcs fell together the repaired regions would overlap until a repair cost as much as a recomputation.

The first half of that holds. The second half does not.

The repair #

The stored potential is the vector of shortest-path distances from a virtual source joined to every vertex at cost zero. After an update, the redrawn arcs are checked. Any arc whose repriced cost is negative is relaxed: $h(v)$ is lowered to $h(u) + w$, and $v$ goes on a queue. Each vertex taken from the queue relaxes its outgoing arcs, and any neighbour whose value falls joins the queue. When the queue empties, every arc is non-negative again, and the potential is a valid one. That is checked over every arc after every repair, not assumed.

An arc whose cost rises never needs a repair. A potential only has to keep repriced costs non-negative, and a higher cost does that more easily. The stored values stop being exact shortest distances, but they remain a valid potential, and Dijkstra only needs validity.

The work is counted in the same relaxation attempts as the full reweighting: one check for each redrawn arc, and one attempt for each outgoing arc of each vertex taken from the queue.

Mended instead of recomputed, the stored potential never stops paying. Across a thousandfold range of churn it costs between 0.647 and 0.710 of running Bellman–Ford for every query. Recomputed, it crosses one at half a per cent and costs 43% more than Bellman–Ford per query at two. The break-even the earlier plate drew was the price of recomputation, not of keeping a potential.

What a repair costs #

A repair after a single broken arc makes about sixteen relaxations and changes about two vertices. At 20% of arcs redrawn between queries, about 400 arcs change at once, and a repair makes 442 relaxations. Almost all of those are the checks of the redrawn arcs themselves. The actual propagation still changes only five vertices.

The prediction expected overlapping repairs to grow into the whole graph, and here they do not, because in this model the damage never spreads. The reason is in how arcs are redrawn. Every cost is drawn as one to nine plus the difference of a hidden potential fixed when the graph was built. That keeps the question answerable, since no cycle can become negative, but it also means every new cost is consistent with the same hidden structure as the old one. A redrawn arc can fall below the stored potential by at most a few units, and the vertex at its head needs to fall by that much and no more. Its own outgoing arcs usually have that much slack, so the change stops there.

The slack distribution is what how long a reweighting stays true measured to explain how often a potential breaks. It also explains how far a break spreads. A fall of a few units at a vertex passes to a neighbour only through an arc whose slack is smaller than the fall. Most arcs have more slack than that, so a repair dies out within a step or two.

That makes the arc model the easy case for a repair, and saying so is part of the result. The flat line on the first plate is partly a property of how the updates were generated. A fair test needs updates whose effects are designed to spread.

Updates that spread #

A different kind of change spreads by construction. Instead of redrawing one arc’s cost, lower one vertex’s hidden potential by up to forty units. Every arc leaving that vertex becomes cheaper by the same amount and every arc entering it dearer. Costs stay consistent with a potential, so no negative cycle appears. But every vertex downstream of the moved one can now be reached more cheaply from the virtual source, and a strongly connected random graph has almost everything downstream of almost everything.

Under this model the repaired region really is the whole graph. A single moved vertex, at 0.4%, already changes 232 vertices’ values on average, and at 2% it is 254 of 256. That is the overlap the prediction expected. The cost still does not reach a recomputation. A repair touching nearly every vertex makes 2,704 to 3,901 relaxations, a quarter to two fifths of the 10,045 a rebuild makes.

The difference is in what each method relaxes. A rebuild from the virtual source runs passes over all 2,009 arcs until a pass changes nothing, five passes here. It relaxes every arc in every pass whether or not its tail moved. The queue relaxes an arc only when its tail’s value has just fallen. A repair that changes 250 vertices, each dequeued once or twice with eight outgoing arcs, makes a few thousand relaxations, because it never looks at an arc whose tail did not change. Covering the whole graph is not the same as scanning it repeatedly.

In total work, the harder model sits near the break-even line with mending and well above it without. A single moved vertex between queries leaves the mended potential at 0.873 of Bellman–Ford per query. The recomputed potential is at 1.349 and has already lost. From about 5% of vertices moving, the mended potential is within a few per cent of breaking even. Here every query breaks the potential, and the repairs cost about a third of a Bellman–Ford run each. A Dijkstra query plus a third of a rebuild comes to roughly one Bellman–Ford run.

The two models bracket the question. In one, a repair touches a couple of vertices. In the other, it touches almost all of them. Real updates presumably fall between: a congestion change raises or lowers one road, and a price change moves everything leaving one node. The repair wins against recomputation at both extremes, by roughly six hundred times at one and three times at the other.

Finding what broke #

A repair has to start from the broken arcs, and finding them has a cost of its own that belongs in the count. Here each update touches a known set of arcs, and only those are checked: one relaxation attempt each, included in every repair cost above. That is what makes the arc model’s 442 relaxations at 20% churn almost entirely checking. About 400 arcs change, each is checked once, and only a handful are found broken.

A system that does not know which arcs changed cannot do this. It would have to scan all 2,009 arcs to find the broken ones, which is two fifths of a full reweighting spent before the repair starts. Most systems that change arc costs do so through an interface that knows which arc it touched, so the cheaper case is the realistic one. It is still an assumption, and a potential shared between a writer that changes costs and a reader that answers queries needs that set passed between them.

The recompute policy on the earlier plate checked the same way. The validity check before deciding to recompute is not charged to either policy, because both need it. The comparison between them is a comparison of what happens after a break is found.

The same waste in landmark tables #

Route search has another kind of stored distance, and it has the same problem. Where the landmarks stand gave a search four tables of exact distances from chosen cells, and what the queries know that the map does not chose those cells from past traffic. A landmark table is a potential in the sense used here: distances from one source, used to price a search. When a cell’s cost changes, the table’s entries downstream of it are wrong.

A landmark bound is a difference of two stored distances, so unlike a potential it can go wrong when costs change in either direction. For falls the repair is the same queue-driven relaxation started at the fallen cell, rises would need values raised, which this repair never does, and the same two cases would apply: a local cost change repairs a few entries, and a change that moves everything downstream repairs most of the table at a fraction of a rebuild. Nothing here measures landmark tables under updates. The mechanism transfers directly, and a system holding several landmark tables pays the rebuild’s cost once per table.

Why a queue and not passes #

The whole difference between the two policies is the shape of the work, and it is worth making precise.

Bellman–Ford from a virtual source runs in passes. Each pass relaxes every arc once, and the passes stop when one changes nothing. On this graph that is five passes of 2,009 arcs. The pass structure is what makes Bellman–Ford correct without any bookkeeping, and it is also what makes it wasteful after a small change: the first pass after an update re-relaxes two thousand arcs to find the handful whose tails moved.

A queue keeps exactly that bookkeeping. A vertex enters the queue when its value falls, and only its outgoing arcs are relaxed when it leaves. A relaxation happens only where something changed one step earlier. Counting on a graph measured traversals that do work in proportion to what they reach and not to what exists, and the repair is a traversal of the same kind: its cost is the degree times the number of times a vertex is dequeued.

That is also why the vertex model’s repairs, which reach nearly every vertex, still cost a third of a rebuild. At 2% of vertices moving, a repair makes 3,322 relaxations and changes 254 vertices, which with eight outgoing arcs a vertex works out to each changed vertex being dequeued about 1.6 times, and costing about thirteen relaxations. Reaching nearly all 256 vertices that way costs about 3,300, against a rebuild that relaxes all 2,009 arcs five times over. The general form is the one the cost is the number of subproblems set out for dynamic programming: after a change, the work that matters is the number of stored values that actually change, and a method that finds only those beats one that recomputes all of them.

Why the earlier crossing was the wrong question #

The earlier essay’s break-even, half a per cent of arcs, looked like a property of a potential under change. It was a property of a policy: throwing the potential away whenever one arc broke it. The repair shows how much of that cost was the policy. Under the arc model the stored potential’s advantage is nearly constant across a thousandfold range of churn, so the crossing disappears. Under the vertex model a crossing exists, near 5% of vertices moving between queries, and it sits there because Dijkstra’s own cost plus a third of a rebuild adds up to one Bellman–Ford.

That last observation is the general form of the result. With repair, a stored potential pays as long as

$$\text{Dijkstra} + \text{repair} < \text{Bellman–Ford from the source},$$

query by query. The repair’s cost is bounded by the size of the region it changes times the degree, not by the graph’s arcs times its passes. On this graph Dijkstra with repriced arcs costs about two thirds of a Bellman–Ford run, so repairs can use up about a third before the stored potential stops paying. What amortised means is the page about spreading a large cost over many operations. Here the large cost has mostly gone. What remains is a per-query cost, and it is small because the queue does work only where values move.

What is settled and what is not #

Settled, by counting on a 256-vertex, 2,009-arc graph over 128 queries, with every repaired potential checked valid on every arc: with arc costs redrawn between queries, mending costs 16 to 442 relaxations per repair and keeps the stored potential at 0.647 to 0.710 of Bellman–Ford per query from 0.02% to 20% churn, where recomputing reaches 1.43. With vertices’ hidden potentials lowered between queries, repairs change 232 to 254 vertices and cost 2,704 to 3,901 relaxations, against 10,045 to recompute. The mended potential there costs 0.87 to 1.04 of Bellman–Ford per query and the recomputed one 1.35 to 1.72.

Not settled:

Queue order. The queue here is first in, first out. The order of a label-correcting repair changes how many times a vertex is re-queued, and a priority queue keyed on the size of the fall might halve the relaxations in the vertex model. It would add heap comparisons, and nothing here measures the trade.

Rises that should be tightened. Rising costs are left alone, since they never break validity. The potential drifts away from exact distances, and a looser potential makes Dijkstra do more work. Some of the vertex model’s slow rise in the per-query ratio as churn grows may be that drift. It is not separated here.

Larger graphs. At 256 vertices a repair covering the whole graph is a few thousand relaxations. On a road network of millions of vertices, a vertex-model change reaches only its own component, and whether that is most of the network depends on the network. The claim here is about one graph size.

Still open: a potential that is never tightened #

The repair lowers values and never raises them, so over a long stream the stored potential becomes a looser and looser bound. A looser potential leaves more slack on arcs, which makes future repairs smaller. It also leaves more slack on the arcs Dijkstra explores, which makes queries larger. Those two effects pull in opposite directions, and the stream length at which a potential should be tightened, by a full recomputation or by a repair that also raises values, is a genuine optimum nobody has measured here.

The measurement that follows runs streams of thousands of queries under both models, with an optional tightening every so many queries. It counts the repairs’ work, the queries’ work and the tightening’s work separately, and it measures the stored potential’s mean distance from exact shortest distances as the stream goes on. The prediction is that under the arc model tightening never pays, because the drift is small, and that under the vertex model there is an interval of a few dozen queries at which a periodic recomputation lowers the total. If both hold, the right policy depends on which kind of change a system sees, and the potential’s own drift is the measurement that tells it which.