Johnson's algorithm
Also known as: Johnson's algorithm · potentials · reweighting · reduced weights · reduced costs · all-pairs shortest paths
An electric car on the streets of Almaty spends energy going up and gets part of it back going down, and some streets have negative weight: Dijkstra goes wrong on such a graph. Johnson's algorithm computes potentials once with Bellman–Ford, rewrites the weights so that all become non-negative, and then runs ordinary Dijkstra. And for the electric car the potential can be seen without Bellman–Ford: it is the height.
An electric car drives through the streets of Almaty. Going uphill it spends energy, going downhill it gets part of it back: the motor works as a generator and charges the battery. The city rises towards the mountains by half a kilometre, and on steep descents the car gets more energy than it spends on the road itself. In the model below there are 1346 such stretches of 20,846: their weight is negative. Dijkstra’s algorithm goes wrong on such a graph, Bellman–Ford will cope but slowly, and if routes between many pairs are needed, very slowly. Johnson’s algorithm computes potentials once with Bellman–Ford, rewrites the weights so that none is negative, and after that ordinary Dijkstra does the work.
The streets appear in the order Dijkstra finds them, and you can see that energy is not the same as distance. Switch regeneration to 0%: descents stop giving energy back, no negative weights remain, and Bellman–Ford converges in one round. Tap an intersection to compare the most economical route with the shortest: the economical one avoids needless climbs, even if the way gets slightly longer.
The idea
Assign each vertex a number p(v), a potential, and replace the weight of each edge with w(u, v) + p(u) − p(v). The weight of any path from s to t changes by one and the same number p(s) − p(t), so shortest paths stay shortest. If the potentials are chosen so that all the new weights are non-negative, Dijkstra can be run on them. Such potentials come from one run of Bellman–Ford.
The model of an 1800 kg electric car is simple. A metre of level road costs 150 mWh, that is, 150 Wh per kilometre. Climbing a metre needs mgh = 1800 · 9.81 · 1 J ≈ 4.9 Wh, and a drive with 90% efficiency spends 5.45 Wh on it. Descending a metre gives back 60% of mgh, 2.94 Wh. A street ℓ metres long with a height difference Δh costs 0.15ℓ + 5.45Δh Wh going up and 0.15ℓ − 2.94Δh going down. If the descent is steeper than about 5%, the second number is negative. The heights of the intersections come from the SRTM radar survey; half the street stretches in the data are steeper than 2%, and one in ten steeper than 5.7%.
Why reweighting spoils nothing
Call the number w′(u, v) = w(u, v) + p(u) − p(v) the reduced weight of an edge.
For any potentials p and any path P from s to t, the reduced weight of the path equals w(P) + p(s) − p(t). So a path is shortest by reduced weights exactly when it is shortest by the original ones, and the weight of a cycle does not change under reweighting.
Let the path pass through the vertices s = v0, v1, …, vk = t. Add up the reduced weights of the edges: Σ (w(vi−1, vi) + p(vi−1) − p(vi)). The potential of each intermediate vertex enters the sum once with a plus and once with a minus and cancels; what remains is p(v0) − p(vk). The addition is the same for all paths from s to t, so the order of paths by weight does not change. A cycle’s start and end coincide, and the addition is zero.
It remains to find potentials that make all the reduced weights non-negative. Add a new vertex q to the graph with an edge of weight 0 from it to every vertex. If the graph has no negative cycles, there is a shortest distance δ(v) from q to every vertex, and Bellman–Ford finds it.
If the graph has no cycles of negative weight, then with p(v) = δ(v) all the reduced weights are non-negative.
For any edge (u, v), the shortest path from q to u continued by the edge (u, v) is one of the paths from q to v, so δ(v) ≤ δ(u) + w(u, v). Move δ(v) to the right: w(u, v) + δ(u) − δ(v) ≥ 0, and that is the reduced weight.
Hence the whole algorithm: Bellman–Ford once, reduced weights, Dijkstra from each vertex needed and the reverse conversion: add p(t) to the distance found and subtract p(s). If Bellman–Ford found a cycle of negative weight, there are no shortest paths, and the algorithm stops there. On the streets of Almaty Bellman–Ford converges in 41 rounds; after reweighting the smallest edge weight is exactly 0, with no negatives.
A potential visible in advance
The electric car has a potential that does not need to be found: height. Take p(v) = 2.94 · h(v) Wh, how much energy a descent from height h gives back. Then the reduced weight of a climb by Δh is 0.15ℓ + 5.45Δh − 2.94Δh = 0.15ℓ + 2.51Δh, and of a descent 0.15ℓ − 2.94Δh + 2.94Δh = 0.15ℓ. In reduced weights a descent costs as much as level road, and a climb costs more by what regeneration will never give back.
Let climbing a metre cost U, descending a metre give back D, a metre of road cost F ≥ 0, and D ≤ U. Then with p(v) = c · h(v) for any c from D to U all the reduced weights are non-negative.
A climb by Δh > 0 along a road of length ℓ: weight Fℓ + UΔh, reduced weight Fℓ + UΔh + c·h(u) − c·h(v) = Fℓ + (U − c)Δh ≥ 0, because c ≤ U. A descent by Δh > 0: weight Fℓ − DΔh, reduced weight Fℓ − DΔh + cΔh = Fℓ + (c − D)Δh ≥ 0, because c ≥ D. Level road: Fℓ ≥ 0.
The listing checks this too: with a potential of 294 mWh per decimetre of height the smallest reduced weight is 150, a metre of level road. The Bellman–Ford potential and the height potential are different, but both will do: their reduced weights differ, while the shortest paths and the distances after the reverse conversion are the same. Knowing the problem saves the whole Bellman–Ford; the first problem below is built on this.
The same technique lies behind A*. The A* heuristic, an estimate of the distance to the target, is also a potential: A* with a consistent heuristic is Dijkstra on reduced weights, where a vertex’s potential is its estimate. Only there the potential is chosen to find the target faster, and here to make the weights non-negative.
A negative cycle is a perpetual motion machine
Shortest paths exist only if there are no cycles of negative weight. For the electric car that would mean a loop through the streets after which the battery is fuller than at the start: a perpetual motion machine. Physics forbids it, and the model shows it too.
If descending a metre gives back no more than climbing a metre costs (D ≤ U), the weight of any cycle is at least F times its length, and there are no negative cycles.
A cycle returns to the same point, so the sum of all climbs on it equals the sum of all descents; call it H. The weight of the cycle is F·L + U·H − D·H = F·L + (U − D)·H ≥ F·L, where L is the length of the cycle.
A climb costs 5.45 Wh per metre because the drive spends more than mgh. Move the share a descent gives back. As long as a descent gives back no more than 5.45 Wh per metre, up to 111% of mgh, there are no negative cycles, and Bellman–Ford converges. Above that is a physically impossible car that gets more going down than it spent going up, and a cycle appears: driving along a street and back becomes profitable if it is steep enough. The first to break, at 130%, is a two-metre bit of street on which SRTM shows a one-metre drop: a survey with a 30-metre step is wrong on such bits. Bellman–Ford notices the cycle because the distances never stop decreasing, and the cycle is recovered from the “came from” pointers.
Code
The listing builds the street graph with energy in whole milliwatt-hours, computes potentials with Bellman–Ford, checks that the reduced weights are non-negative and that height also works as a potential, and builds an energy table between five places: five runs of Dijkstra. At the end, the shortest and the most economical route from the Central Stadium down to the Green Bazaar.
The table is asymmetric. From Republic Square to the Central Stadium, 49 metres down, it is 274 Wh, and back 685. From Kok-Tobe to Almaty-2 station the car descends 174 metres and spends 1148 Wh, while the way back costs 2608. The shortest way from the stadium to the bazaar is 5.71 km with 47 metres of climbing and 810 Wh; the most economical is slightly longer, 5.75 km, climbs only 18 metres and spends 742 Wh, 8% less.
What it costs
| Method | Time | On the streets of Almaty (V = 7909, E = 20,846) |
|---|---|---|
| Bellman–Ford from each vertex | O(V2E) | up to 1012 relaxations |
| Floyd–Warshall | O(V3) | 5·1011 operations |
| Johnson: Bellman–Ford once and Dijkstra from each vertex | O(VE + V(V + E) log V) | 41 rounds of Bellman–Ford, then V times ~3·105 operations, about 2·109 |
| Johnson with the height potential | O(V(V + E) log V) | no Bellman–Ford at all |
The sparser the graph, the bigger the gain. On a dense graph, where E ≈ V2, Johnson and Floyd–Warshall are comparable, and Floyd–Warshall is simpler. And if the answers are needed not for all pairs but for a few sources, Johnson pays only for them: Bellman–Ford once, Dijkstra as many times as there are sources. Memory is O(V + E) for the graph and the potentials; the table of all pairs is a separate O(V2).
Where else potentials work
Flows and assignments. The minimum-cost flow algorithm by shortest paths recomputes the potentials after each step so that no negative edges appear in the residual network; this is how Jack Edmonds and Richard Karp did it in 1972. Exactly this mechanism works in the Hungarian algorithm: its potentials of couriers and orders are the same numbers p.
A* and landmarks. The A* heuristic is a potential; the ALT method computes it from the distances to a few landmarks and the triangle inequality.
Graphs without cycles. If a graph is acyclic, negative weights are no threat at all: shortest paths are found in one pass in topological order, with neither Bellman–Ford nor Dijkstra.
Paths that change. When weights change a little, the old potentials often stay almost right: after recomputation there are few negative edges, and the potentials are repaired locally, without running Bellman–Ford anew.
History
Reweighting by potentials appeared in flow problems: in a somewhat different form in Delbert Fulkerson’s work in 1961, then in Nobuaki Tomizawa’s in 1971 and in that of Edmonds and Karp in 1972. Donald Johnson applied it to all-pairs shortest paths, first in a 1973 report, then in the 1977 paper “Efficient algorithms for shortest paths in sparse networks”, which itself cited the work of Edmonds and Karp. The name “Johnson’s algorithm” stuck to the combination: one Bellman–Ford, reweighting and Dijkstra from each vertex.
Problems
In the first problem the potential does not have to be found: it is given in the statement as heights, and Bellman–Ford would not make it in time on such a graph. The second is the real Johnson’s algorithm on a graph with arbitrary negative weights.
An electric car in the hills A table between stationsData: Almaty roads © OpenStreetMap contributors, ODbL Heights of Almaty's crossings: NASA SRTM v3 (1″) via Open Topo Data, public domain