Potential function — where it appears
Named by 9 essays across 2 fields — each of them below, with the objects they name alongside it.
What amortised means
Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws.
An estimate is a reweighting
Reprice every arc by the estimate's drop across it and run plain Dijkstra, and it expands the same 325 cells A* does, in the same order, because the two are one algorithm. Replace the estimate with one that is still never too high but drops too fast between neighbours, and 215 arcs go below zero — and on a stated grid the search that refuses to reopen a finished cell returns a path of 178 where the shortest is 169.
Two estimates that must agree
Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.
One Bellman–Ford buys every Dijkstra
A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.
Where the landmarks stand
Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.
What the queries know that the map does not
A greedy rule that chooses landmark cells by rerunning a sample of past queries needs two hundred of them to draw level with a rule that reads only the map — and what it finally chooses, on map after map, is the four corners. Give the queries a destination instead of scattering them, and twenty are enough to beat the corners by 29% on eight maps out of eight. A query log is worth reading exactly to the extent that it is not uniform.
A stop that is correct and never sooner
A two-ended search can stop when the two frontiers' keys together reach the best route found, and it can also stop when either frontier's own estimate reaches it alone. Both rules are safe, so a search may use whichever fires first. On forty weighted grids the second never fires: at the moment the first one stops the search, the larger of the two own-keys stands at 64% of the route. The extra rule costs 60% more counted work and a second priority queue to find that out.
How long a reweighting stays true
Johnson's one Bellman–Ford run costs under one per cent of an all-pairs computation because it is divided over every source. Asked one query at a time it is divided over nothing, and it still repays itself after 2.7 queries — because the preparation is one Bellman–Ford and every query saves a third of another. What decides the trade is not the query count but whether the graph holds still: at half a per cent of arcs redrawn between queries the stored potential is worth exactly nothing, and its life is geometric at a per-arc failure rate of 6.6%.
A potential mended where it broke
A stored reweighting on a 256-vertex graph with negative arcs costs 10,045 relaxations to rebuild, and rebuilding it every time an update breaks it stops paying once half a per cent of arcs change between queries. Mending it from the arcs that broke costs 16 to 442 relaxations instead, and the stored potential stays at two thirds of the per-query cost at every rate of change. When the change is a vertex whose costs all move together, a repair reaches nearly every vertex. It still costs a third of a rebuild.
Named alongside it
The objects these essays reach for when they reach for this one.
Shortest pathHeuristic searchReweightingAdmissibilityBreak-evenDijkstra's algorithmNegative weightTriangle inequalityPreprocessingRelaxationSearch frontierSpace time trade