One Bellman–Ford buys every Dijkstra

An estimate is a reweighting showed that A* is not a different algorithm from Dijkstra’s. Give every vertex a potential — the estimate of its distance to the goal — and reprice each arc from $u$ to $v$ by its cost plus the potential at $v$ minus the potential at $u$. Along any route the potentials telescope, so every route between two fixed vertices changes cost by the same constant and the shortest route does not move. Dijkstra on the repriced arcs expands the cells A* expands, in the order A* expands them. And the repriced arcs are non-negative exactly when the estimate is consistent, which is exactly Dijkstra’s precondition.

That essay pointed out that the construction does not need the potential to be an estimate. It needs a function whose change across every arc is no more than the arc’s cost. If a graph has negative arcs, Dijkstra’s precondition fails outright — the bound with a precondition showed it returning a wrong answer on four vertices with one negative arc — but a potential that makes every repriced arc non-negative would restore it, for every source at once.

Johnson’s algorithm computes such a potential. This page measures what it costs and what it buys against the two methods it competes with for all-pairs shortest paths on graphs with negative arcs.

The potential that is already a shortest path #

The construction is short. Add one new vertex joined to every vertex by an arc of cost zero, and run Bellman–Ford from it. Call the distance it finds to each vertex $h(v)$. Every $h(v)$ is at most zero, and for every arc from $u$ to $v$ of cost $w$,

$$h(v) \le h(u) + w,$$

because a route to $v$ through $u$ is a route to $v$, and $h(v)$ is the shortest. Rearranged, $w + h(u) - h(v) \ge 0$. So repricing each arc by the potential $h$ makes every arc non-negative, and it is exactly A*'s repricing with $-h$ in the role of the estimate. The triangle inequality that makes an estimate consistent is here a theorem about shortest paths, and it holds for every arc automatically.

After repricing, Dijkstra runs from each vertex in turn, and each distance it finds is converted back by adding $h$ at the far end and subtracting it at the near end. One Bellman–Ford and $V$ Dijkstras, where the alternative is $V$ Bellman–Fords.

The plate is the reweighting with a supplied potential, and the two searches it compares are one search. Johnson’s algorithm is the same construction on a graph where the potential has to be found first, because no one can write down a consistent estimate for a graph whose arcs are negative.

The graphs, and what is counted #

The graphs are directed, with 256 vertices, and each vertex draws a stated number of out-arcs to vertices chosen at random. Each arc costs a whole number from one to nine plus $p(u) - p(v)$ for a random hidden potential $p$ between 0 and 39. That second term makes a third or more of the arcs negative — 189 of 507 on the sparsest graph, 15,173 of 41,088 on the densest — while every cycle keeps its original cost, since the hidden potentials telescope around it. So the graphs have many negative arcs and no negative cycle, by construction rather than by luck.

Three methods compute every distance:

• Bellman–Ford from every source, each run with the early exit that stops when a pass over the arcs changes nothing;
• Johnson’s reweighting: one Bellman–Ford from the added vertex, then Dijkstra with a binary heap from every source on the repriced arcs;
• Floyd–Warshall: for every intermediate vertex, for every pair, keep the smaller of the direct distance and the distance through that vertex.

The count is the same unit throughout the field where it applies — arc relaxations tried — plus the comparisons the heap makes, and Floyd–Warshall’s count is its $V^3$ comparisons of a distance with a distance through an intermediate. All three methods’ answers are compared entry by entry, 65,536 of them per graph, and they agree on every graph drawn.

The count against density #

Three lines and two crossings, one of which is the surprise.

Floyd–Warshall is flat and never the cheapest. Its count is $V^3$ whatever the graph, 16.8 million at 256 vertices, because its three loops run over every triple regardless of which arcs exist. Johnson’s reweighting is below it at every density drawn, and repeated Bellman–Ford is below it until an out-degree of 128.

Johnson’s reweighting wins from an out-degree of eight. At 255 out-arcs a vertex it is half the cost of repeated Bellman–Ford, 13.1 million against 25.8 million, and the ratio stays near a half from 64 upwards.

Repeated Bellman–Ford wins on the sparsest graphs. At out-degree two it costs 594,269 against Johnson’s 647,489, and at four, 1,357,716 against 1,402,193. Running the “slow” algorithm 256 times beats running the “fast” one 256 times after a one-off preparation.

Why the early exit wins sparse #

The textbook comparison says Bellman–Ford costs $V \cdot E$ per source and Dijkstra with a heap $E \log V$, so Johnson’s reweighting should win everywhere by a factor of about $V / \log V$. The measurement disagrees at the sparse end because the textbook Bellman–Ford is not the one anybody runs.

The textbook bound allows 255 passes per source. The measured runs make between three and nine. The bound with a precondition found the same thing on a single source — seven passes of the 2,047 allowed on a graph of 2,048 vertices — and the reason is that Bellman–Ford with an early exit needs only as many passes as the shortest paths have arcs. On a random graph most shortest paths are short in arcs, and the denser the graph the shorter they get: 2.95 passes on the densest graph means most distances are settled within three arcs of the source.

So repeated Bellman–Ford costs about $V \cdot E \cdot P$, where $P$ is that small and falling number of passes, and Johnson’s reweighting costs about $V \cdot E$ relaxations — one per arc per source — plus the heap’s comparisons. On the sparsest graph the arcs are so few that the heap is most of Johnson’s cost: 544,096 of its 647,489 at out-degree two. Nine passes over 507 arcs from each source is cheaper than a heap that has to order every vertex a source reaches. As the graph fills in, $E$ grows by a factor of eighty while the heap’s work grows by a factor of about four and a half, and Johnson’s count comes to be dominated by relaxations, one per arc, where Bellman–Ford’s is three per arc.

The counts can be read against that account directly. On the densest graph repeated Bellman–Ford makes 25,754,326 relaxations against $V \cdot E$ of 10,518,528, a ratio of 2.45, while its passes average 2.95. The ratio sits below the passes for two reasons, both visible in how the method is written. The first pass relaxes arcs only out of vertices already reached, and on the first pass from a source that set starts at one vertex and grows as the pass proceeds, so the first pass touches only part of the graph. And the last pass is the one that changes nothing — it relaxes every arc and learns only that it can stop. On a graph where distances settle in two passes, the method pays for a third to find that out.

Johnson’s Dijkstra runs have no such final pass. Each one relaxes the arcs out of each vertex exactly once, when that vertex leaves the queue, and stops when the queue is empty, so its relaxations are exactly $E$ per source. What it pays instead is the heap: each vertex reached is pushed and popped, at a comparison or two per level of the heap on the way in and on the way out. That is about 2,100 comparisons per source on the sparsest graph and about 9,600 on the densest, and on the sparsest graph those comparisons are 84% of Johnson’s whole count — which is exactly why the method that uses no queue at all wins there.

The preparation is the part of Johnson’s algorithm that sounds expensive and is not. Its one Bellman–Ford run is under one per cent of the total at every density drawn. Paying a whole Bellman–Ford once, to make every one of 256 later searches cheaper, is an easy trade when the thing being bought is 256 searches.

Floyd–Warshall, and what the count does not see #

Floyd–Warshall losing the count at every density is worth being careful about, because its reputation for dense graphs is not wrong. It is about something this count does not charge.

Its $V^3$ is exact: the three loops always run. Johnson’s count at the densest graph is 10.6 million relaxations and 2.5 million heap comparisons, and the relaxations are exactly one per arc per source plus the preparation’s — 256 times 41,088, plus 124,288. The generator draws 255 random out-arcs per vertex with repeats, which leaves 41,088 distinct arcs of the 65,280 a complete graph would have: 63%. If every arc were present, Johnson’s relaxations alone would be $V \cdot V(V-1)$, close to $V^3$, and with its heap comparisons added it would pass Floyd–Warshall. Extrapolating from the measured heap cost, the crossing falls at about 85% of all possible arcs, a density the plate does not reach.

The other thing the count does not see is where the operations land in memory. Floyd–Warshall’s inner loop compares one row of the distance matrix with another, element by element, in order — a sequential sweep of two arrays, which is the access pattern a cache handles best. Johnson’s algorithm follows adjacency lists and sifts a binary heap, both of which jump across memory. A list and a block of memory measured a factor of 3.6 in modelled cache misses between two layouts of the same traversal, and the count is not the time is the site’s standing warning that a gap in operations can be reordered by a gap in misses. So the counts on this page say Floyd–Warshall is never the cheapest in operations up to 63% density; they do not say it is slower, and on a real machine at high density it may well not be.

The same comparison at twice the size #

Doubling the vertices keeps both crossings where they were — repeated Bellman–Ford still wins at out-degree two and loses by eight — and makes Floyd–Warshall’s position worse at the sparser densities, since its count grew by a factor of eight while the other two grew by between four and five there; at the densest graph all three grew by between seven and eight. Two parameters, one bound, no order is the reason no single ranking survives: the costs are functions of $V$ and $E$ together, and which is cheaper is a question about the graph’s density, not about the algorithms.

Choosing by density, and what the choice depends on #

The plates make a rule that can be stated in one line, and it is worth stating along with what it rests on. On these graphs, below an average of about eight out-arcs a vertex, run Bellman–Ford from every source; from eight to well past sixty per cent of all possible arcs, reweight once and run Dijkstra; and only near a complete graph does Floyd–Warshall’s fixed $V^3$ come into contention on the count.

Every boundary in that rule is a property of the graphs rather than of the algorithms. The first boundary depends on how many passes Bellman–Ford needs, which depends on how many arcs shortest paths use, which on a random graph is small and on a road network is not. The second depends on how many arcs exist against how many could. And neither boundary depends on the negative arcs at all: they make Dijkstra unusable without the preparation, but once the preparation is done, the counts are the counts of Dijkstra on a graph with non-negative costs. The negative arcs decide that a preparation is needed; the density decides whether it pays.

That separation is the same one two parameters, one bound, no order insists on for every graph bound: a cost in $V$ and $E$ is not ranked against another until a regime is named. The textbook ranking of these three methods — Floyd–Warshall for dense graphs, Johnson for sparse ones, Bellman–Ford for neither — names no regime and is wrong at both ends of the plate.

Where the reweighting sits among the field’s other repairs #

A graph with negative arcs has now been handled three ways, and each repair removes a different obstacle.

The precondition that removes the queue handled a graph with no cycles at all: relax the arcs in topological order, once each, and negative costs do not matter. A graph is as hard as its largest cycle handled a graph with cycles by breaking it into strongly connected components, running Bellman–Ford inside each, and relaxing the arcs between components in topological order.

The three repairs answer different questions. The topological order and the components-first method are single-source methods that make Bellman–Ford cheaper by giving it less to do. Johnson’s reweighting does not make Bellman–Ford cheaper at all; it runs it once, in full, and uses the result to make negative arcs disappear, so that every later query can use a method that could not have handled them. It is a preparation that turns a precondition from something the graph must satisfy into something the algorithm arranges.

That is the same move the site’s estimate essays made, seen from the other side. An estimate is supplied and makes one query faster; Johnson’s potential is computed and makes every query possible. Both are functions on vertices whose differences across arcs are bounded by the arcs’ costs, and the property that makes one kind of function useful makes the other correct.

What the model leaves out #

Graphs with negative cycles. The generator cannot produce one. Johnson’s single Bellman–Ford detects a negative cycle — a pass on the last round still changes something — and the method stops, as it must, since shortest paths are then undefined. Repeated Bellman–Ford would detect it from every source that can reach it, which is more work to learn the same fact.

A heap is not the only queue. The queue decides the class measured three priority queues for Dijkstra and found a factor of 37 between them on one graph. On the sparsest graphs here the heap is most of Johnson’s cost, and a cheaper queue would move the crossing with repeated Bellman–Ford towards sparser graphs still.

Random graphs only. Bellman–Ford’s early exit is cheap because shortest paths on a random graph are short in arcs. On a graph whose shortest paths are long in arcs — a road network, a long chain with shortcuts — the passes per source rise towards the number of vertices, and repeated Bellman–Ford loses everywhere.

Still open: when the queries are not every pair #

Johnson’s preparation costs under one per cent of its total because it is divided over 256 sources. A system that answers shortest-path queries one at a time, as they arrive, on a graph with negative arcs faces a different trade: one Bellman–Ford run against however many queries eventually come. If the queries are few, a Bellman–Ford per query is cheaper; if they are many, the one-off reweighting is. And a graph that changes — an arc’s cost updated — can invalidate the potential, so the preparation may have to be repaid.

The measurement that follows prices a stream of single-source queries on these graphs, with and without a stored potential, and finds the number of queries at which the preparation pays for itself — and then updates a stated share of arc costs between queries and asks how often the stored potential stays valid, since an update that keeps every repriced arc non-negative does not require recomputing it.