Shortest path — where it appears
Named by 27 essays across 2 fields — each of them below, with the objects they name alongside it.
The precondition that removes the queue
Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.
The precondition on a function the caller writes
Dijkstra expands 1,582 cells to find a path of 98 across a fifty-square grid. The same loop, with the straight-line distance to the goal added to each key, expands 405 and finds the same 98. The estimate has to be a function the caller supplies, and the guarantee holds only while that function never overestimates — a condition on somebody else's code, not on the graph.
A distance that is a path through a grid
How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.
A graph is as hard as its largest cycle
Negative arcs rule out Dijkstra's algorithm and leave Bellman–Ford, which on a thousand vertices does three million units of work. Stopping it when a pass changes nothing brings that to 78,496. Finding the strongly connected components first and running it inside each one brings it to 38,549 — and to a quarter of the early-exit cost when the components are small, because every cycle lives inside one.
An estimate borrowed from an easier problem
On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.
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.
Where two searches should stop
Search from both ends of a shortest-path query at once and the two frontiers meet somewhere in the middle, having expanded about two thirds of what one search would. Stop at the first vertex both searches have finished, and on five of forty weighted grids the path returned is longer than the shortest. The rule that is always right stops on a different condition, and on one of those grids it also stops sooner.
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.
A placement after the traffic moved
Four landmarks fitted to twenty queries that all end at one cell expand two thirds of the corners' cells there. Move the destination ten cells and the advantage is gone; move it thirty and the fitted placement expands nearly twice the corners' cells. Choosing again costs 317,000 cells of search — the saving of 8,600 queries — so on streams whose destination drifts, a policy that refits on a counter never beats fitting once and keeping the result, and past a drift of about ten cells nothing fitted beats the corners.
A refit that changes one landmark
Choosing four landmarks again after traffic moves costs hundreds of thousands of cells of search, and on drifting streams it never paid. Keeping three and re-choosing the fourth costs a fifth as much — 0.19 of a full selection, not the twelfth the earlier page guessed. On drifting streams, refitting on the counter goes from a loss of up to 13% to within 2% of fitting once, and it wins where the destination moves six cells. When the destination jumps, it is the cheapest policy measured, 12% under the corners at one jump in 10,000 queries — unless the jumps come as often as one in 2,500.
The candidates near where the queries end
Re-choosing one landmark after the traffic moves tried every candidate as the replacement, and most of them could not win. Tried only on the four candidates nearest the new destination, the refit costs 0.085 of a full selection — the twelfth an earlier page guessed — against 0.236, and its placements serve fresh queries within 3% as well. Where the full search's winner lies further away, the refit was barely worth making. A refit that cheap still cannot follow a destination that jumps every 2,500 queries; what holds the counter back was never the refit's price.
Starting from the corners
A landmark search that refits one landmark when its traffic moves lost to the fixed corners when the destination jumped often, and the accounting blamed the one full selection every refitting policy makes at the start. Starting from the corners instead, and never selecting in full, closes 82% of that gap at one jump in 2,500 queries and is the cheapest policy of all at one in 5,000. It gives the full selection back its advantage when jumps are rare, and on traffic that drifts a step at a time it gives up fitting altogether. Its counter fires when the cost rises, and from the corners concentrated traffic raises nothing: the corners are no worse for it, only no better.
A refit priced before it is made
A landmark placement that starts at a maze's corners and refits one landmark when a counter sees recent queries getting dearer closed most of its gap on traffic that jumps — and on traffic that drifts it never fired, because from the corners concentrated traffic raises no cost. The chance it missed is cost that could fall. Pricing that chance directly — the current placement on the last twenty queries against four nearby candidates, every two thousand queries, refitting when the estimated saving pays for the refit — costs 120.5 cells a query at one jump in 2,500 against the counter's 128.9 and the corners' 126.8, and 107.4 on a slow drift against 103.3 for a full selection fitted once. It fails where jumps come every thousand queries, and on one stream it stops firing after its placement has aged.
A horizon the stream can supply
A watch that refits a landmark placement when an estimated saving pays lost where traffic jumped every thousand queries, because its estimate assumed each saving would last a whole window. The horizon proposed to correct it, learned from the intervals between the watch's own refits, is the window every time: the watch looks once a window, so its refits are never closer together than one. A horizon learned from the traffic instead — how long it stays within ten cells of one destination — is safe on every stream and saves 3.4% at one jump in 2,500. At one in 1,000 it reaches 150.7 cells a query against the corners' 142.7, and a horizon read from the future only ties them. At that pace the looking costs what the refits save.
A watch that looks less
A landmark watch that refits when an estimated saving pays loses to the plain corners when traffic jumps every thousand queries, because its looking costs more than its refits save. Using its learned horizon to look less often there — doubling the interval when the horizon falls below half of it, halving it when the horizon comes back — was predicted to tie the corners at that pace and cost nothing elsewhere. It ties nothing: 150.5 cells a query against the corners' 142.7, since the looks it skips are the looks that found the chances. And at one jump in 2,500, where the watch had won, it loses by twenty cells, because the rule cannot come back down. Halving needs a horizon as long as the stretched interval, and at 8,000 queries no stream here supplies one. A two-state rule that can come back does better and still loses at both paces. The looking was never the waste; at one jump in 1,000 there is nothing to watch for.
A watch that switches itself off
A landmark watch that cannot beat the plain corners by looking less was given a switch instead: at every look it prices the corners on the same twenty queries, and when the corners would have been cheaper over its last four looks it goes back to them and stops looking for 8,000 queries. At one jump in 1,000 it works — 145.5 cells a query comparing search costs, 144.4 charging the watch for its own looking and refits, against the corners' 142.7 and the watch's 150.7. At one jump in 2,500, where watching pays, both switches give the watch's advantage away, 125.3 and 126.1 against 116.4, and the charging switch is off for 60% of the stream, as much as at the fast pace. What a look reads is the same at both paces: 12,249 cells a window at one, 11,257 at the other, with a spread of sixty thousand. The watch's value arrives in a few large looks after jumps, and four looks at any pace are mostly the others.
A switch that counts the jumps
A landmark watch whose switch read its own costs could not tell fast traffic from slow, because what a look reads has the same mean at both paces. A switch that reads the traffic instead — the mean spacing of the last ten times the destination moved more than ten cells — was predicted to reach the corners at one jump in 1,000 and keep the watch at every slower pace. It separates the paces where costs could not: 146.6 cells a query at one jump in 1,000 against the watch's 150.7, and on drifting traffic it never switches off at all. But a count of k events is a reading with a delay of k events and a noise of one part in √k, and no k has both: three stretch ends reach the corners' 142.7 at the fast pace and are off 38% of the slower stream; twenty never misfire and save nothing. And when traffic slows, the events that would show it stop arriving, so the count keeps its fast reading and the switch stays off: 135.8 cells a query on a stream that slows halfway, worse than the corners or the watch.
A switch that hears the traffic stop
A landmark watch switched off by a count of the traffic's stretch ends cannot see traffic slow down, because a slowing is the events stopping, and a count of events keeps its last reading. Letting the open spacing since the last stretch end into the reading, once it is longer than the recorded ones, was predicted to turn the watch back on within four thousand queries of a slowing and cost nothing on steady traffic. It costs nothing on steady traffic, and on ten stretch ends it hears the slowing late, after three to eleven thousand queries, because the silence is averaged with nine fast spacings. On five or three it hears it in time, and the switch on five comes within two cells of the best known policy on every stream.
A silence that overrules the count
A landmark watch switched to the corners by a count of the traffic's stretch ends heard a slowing only once the silence outweighed the fast spacings it was averaged with, about 5,900 queries on ten stretch ends. Letting an open spacing of 1,600 queries overrule the count outright was predicted to make the count's length stop mattering on the stream that slows. It hears the slowing within a thousand queries at every count from three to ten, and keeps the corners 8% of the slow half where the count kept them 65 to 75%; the counts still differ, by 3.4 cells a query, because the fast half is where a short count keeps the corners that pay. On the stream that speeds up the override is the cheapest switch at every count, and on steady traffic it is within a cell and a half of the silence.
A gap between off and on
A landmark watch switched to the corners whenever a count of the traffic's last stretch ends read under 1,600 queries, and back on when a silence of 1,600 overruled the count. A count that only decides when traffic is fast need not use the silence's threshold, so a second, lower one was given it: keep the corners only once the count reads under 1,200. At one jump of the destination in 2,500 queries, on three stretch ends, that saves 3.5 cells a query — 117.8 against the override's 121.3 — but keeps the corners 13% of the time, not under 5%, and stays 1.4 cells above the watch rather than within one. At one jump in 1,000, where the corners are right, the gap costs 1.7 cells; on five stretch ends it saves nothing anywhere; and at slower paces, on traffic that changes pace and on drift, it changes nothing. The two jobs do want two numbers, but only one count length wants them.
A margin the count sets itself
A landmark watch switched to the corners when a count of the traffic's stretch ends read fast saved 3.5 cells a query at a moderate pace once given a second, lower threshold for switching off — but only on a count of three, and at a cost at the fast pace. A fixed gap is the same at every count, so the gap was set by the count instead: switch off only when the reading plus Z of its own standard errors is under 1,600. At one standard error on three stretch ends it makes exactly the fixed gap's choices, 117.8 cells a query at one jump in 2,500 and 144.5 at one in 1,000 — losing 1.9 to the override at the fast pace where under one was predicted, because fast spacings are bunched, not similar. Averaged over six streams every switch on three or five stretch ends lies within about a cell and a half of the best, 113.8: the off threshold, however it is chosen, trades the moderate pace against the fast one, and the count's length decides more than its margin.
Named alongside it
The objects these essays reach for when they reach for this one.
Heuristic searchLandmarkBreak-evenParameter choiceQuery distributionPreprocessingDijkstra's algorithmHonest limitPotential functionRegimeStopping ruleAdmissibility