Algorithms & Data Structures
the bound is a claim, and it is checkable
Field

Two parameters

A graph's cost is in V and E, so no bound here is a comparison until the density is stated. The same two algorithms change places when only the shape of the graph changes.
10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

Counting on a graph

The counted graph this site's second field is built on, why an array's primitives do not generalise, and the first result it produces — that BFS and DFS differ in no measurement of time at all.

 sparse, fixed average degree10010³10³10⁴10⁵10⁶VworkDijkstra, binary heap — E log EDijkstra, all V queued — V^2dense, fixed density10010⁴10⁵VworkDijkstra, binary heap — V + EDijkstra, all V queued — Ethe class is a property of the sweep as much as of the algorithmwork = scans + visits + relaxations + queue comparisons

Two parameters, one bound, no order

Why a graph bound is not a comparison until the density regime is stated, what a fit in two variables has to do differently, and the measured case where a published class stops describing the algorithm.

 adjacency scansrelaxationsqueue comparisonsvisitsBreadth-first14,336Dijkstra, all V queued2,118,656Dijkstra, binary heap56,973Bellman–Ford, all passes50,309,120Prim64,884Kruskal74,008V = 2048, E = 6,144, sparse, fixed average degreeevery segment counted exactly

The queue decides the class, and the pseudocode does not name it

Three priority queues inside one algorithm, counted separately from the traversal, and the two implementation decisions that decide a complexity class without appearing in any published statement of it.

 10³10⁴11010010³npointer hops per findneitherpath compressionunion by rankboth3n random unions, seededα(n) ≤ 4 for every n on this axis

The constant that is practically constant

The four combinations of union by rank and path compression, measured; what α(n) actually is when it is tabulated rather than quoted; and the one case on this site where the formal class overstates rather than understates.

 10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons

The precondition that removes the queue

Shortest paths on an acyclic graph, where the topological order is the priority order, the queue has nothing to decide, and the precondition buys something instead of costing it.

 adjacency scansrelaxationsqueue comparisonsvisitsKosaraju, two passes5,632Tarjan, one pass2,560V = 1024, E = 1,536, directed, components plantedevery segment counted exactly

Two passes or one, and what the second one costs

Two component algorithms measured against each other — the arcs each examines, the stack one of them holds, and the ordering both of them hand back in opposite directions.

 No estimate543 cells expanded · path 58Straight-line estimate325 cells expanded · path 58Estimate doubled71 cells expanded · path 64V = 900, E = 895, every edge costs onethe estimate is a function of the vertex, supplied by the caller

The precondition on a function the caller writes

A* measured against Dijkstra on the same grids, the dial between an admissible estimate and a fast one, and what a precondition looks like when it is about a function rather than about an input.

 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph

A list and a block of memory

Adjacency lists against compressed sparse row, with identical counted work and modelled miss counts a factor of 3.6 apart — the two-counts theme at the widest separation it reaches here, and where it fails to.

 busiest vertexuniform pairsbusiest 16 · Σd² 43,104 · degeneracy 4attachmentbusiest 114 · Σd² 90,296 · degeneracy 4pairs of neighbours examineduniform pairs — every pair18,480uniform pairs — oriented4,090attachment — every pair42,076attachment — oriented3,339V = 1,024, E = 3,072 on both30 triangles and 249 — the answers, which also differ

Two parameters are not enough either

Triangle counting on two graphs a two-parameter bound cannot tell apart, the sum of squared degrees that decides the naive method, and the degeneracy that bounds the oriented one.

 10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapBellman–FordBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

The bound with a precondition

Two shortest-path algorithms whose published bounds describe versions nobody runs, the four-vertex graph on which the faster one is simply wrong, and what an algorithm's generality costs when it is measured rather than assumed.

 24816326410⁵10⁶components the graph is built fromcounted workcomponents firstBellman–Ford, early exitBellman–Ford, every passV = 1,024, negative arcs between componentsvertices relabelled at random

A graph is as hard as its largest cycle

Shortest paths with negative arcs, taken one strongly connected component at a time. Bellman–Ford pays for the whole graph's cycles; the component method pays only for the largest component's, and on a randomly numbered graph it beats the early-exit Bellman–Ford by up to five times while returning identical distances.

 cells expandedreads building the estimateNo estimate1,572 expanded · path 356Straight-line estimate1,550 expanded · path 356A*, landmarks252 expanded · path 356 · 6,328 reads to buildV = 2,500, steps cost one to nine, seed 20260910shortest path 356

An estimate borrowed from an easier problem

A* with the straight-line estimate against A* with landmark distances, on unit grids and on weighted terrain. The straight line is the exact answer to a problem with no terrain in it, and a landmark table is the exact answer to one that has the terrain, which is why one collapses on weighted ground and the other does not.

 cells expandedNo estimate543 expanded · path 58Straight-line estimate325 expanded · path 58Dijkstra, reduced costs325 expanded · path 58 · 0 arcs priced below zeroV = 900, unit steps, seed 20260910shortest path 58

An estimate is a reweighting

A* with a consistent estimate is Dijkstra on reduced arc costs, checked expansion for expansion. An estimate that is admissible but inconsistent makes some reduced costs negative, breaks Dijkstra's precondition, and returns a longer path unless finished vertices may be reopened — which costs more expansions than the consistent estimate needed.

 stop where they meetextra path length42321stop when keys reach itextra path length110203040grid, by seedV = 900, 28% blocked, steps cost one to nine5 of 40 wrong under the meeting rule

Where two searches should stop

Bidirectional Dijkstra with two stopping rules, measured over many grids. Stopping where the searches meet returns a longer path on weighted terrain one time in eight; stopping when the frontiers' smallest keys together reach the best route across any arc is always right, and expands 64 to 75 per cent of what a one-ended search does rather than the half the geometry promises.

 ordered by degreedegeneracy orderthe degeneracy024681012largest out-degreeuniform pairs, degree 452 above duniform pairs, degree 6136 above duniform pairs, degree 1083 above dpreferential attachment, degree 414 above dpreferential attachment, degree 622 above dpreferential attachment, degree 1058 above d1,024 verticesdashed: the degeneracy

A bound right for the wrong reason

The degree orientation used for triangle counting, measured against the degeneracy it is said to be bounded by. Its out-degrees exceed the degeneracy on every graph drawn, so the usual argument for its O(E·d) bound is false; the bound holds through the sum over edges of the smaller endpoint degree. An orientation taken from the degeneracy computation itself keeps every out-degree at or below d and examines 5% to 25% fewer pairs.

 steps cost one to ninesteps cost one01,0002,0003,000cells expanded, mean over the gridsA* from one endalways shortestalways shortesttwo-ended Dijkstraalways shortestalways shortesttwo A*, separate estimateswrong on 12always shortesttwo A*, stop on either keyalways shortestalways shortesttwo A*, averaged potentialalways shortestalways shortest40 grids a bar, 2,500 cellsestimate: straight-line cells

Two estimates that must agree

Two-ended A* on weighted and unit-cost grids, combined three ways. Separate estimates with the sum stopping rule stop too early on 12 of 40 weighted grids; a rule that waits for either frontier alone is correct and expands three times as much; an averaged potential is correct on every grid and costs 4% more than the incorrect search — while on unit-cost grids none of the combinations improves on A* from one end.

 24816326412825510⁶10⁷average out-degreecounted workBellman–Ford from every sourceJohnson's reweightingFloyd–Warshall256 vertices, every answer comparedwork: relaxations + heap comparisons

One Bellman–Ford buys every Dijkstra

All-pairs shortest paths on directed graphs with negative arcs and no negative cycle, by Bellman–Ford from every source, by Johnson's reweighting and by Floyd–Warshall, counted against density at 256 and 512 vertices. Johnson's reweighting is the same construction as A*'s potential with the potential computed rather than supplied; its preparation is under 1% of its work, it wins from an average out-degree of eight, and repeated Bellman–Ford wins below that.

 0200400600800cells expanded per query, meanno landmarks897four near the centre423four at random209farthest-first141the corners1268 maps × 150 queriesdots: each map's mean

Where the landmarks stand

The landmark estimate for A* on weighted grids, with its landmark cells placed at the corners, near the centre, at random and by farthest-point selection, and with one to eight of them. Placement changes the cells expanded per query by a factor of 3.4 at a fixed number of landmarks; the corners beat farthest-point selection on every map, because farthest-point selection's fourth landmark lands in the interior.

 125102050100200100observed queries the selection sawcells expanded, meanon fresh querieson the sample it was chosen fromthe cornersfarthest-first8 maps × 150 fresh queriesflat lines read no queries

What the queries know that the map does not

Greedy landmark selection from a sample of observed queries, measured against corner placement on eight weighted maps, under uniform queries and under queries drawn to one, two, four and eight destinations — with the preparation priced in the same unit it saves.

 0.000.250.500.751.0005001,0001,500by key60% forward70% forward80% forward90% forwardone-endedhow the expansions are sharedcells expandedseparate key ÷ route40 grids, 2,500 cellsdashed: how close the separate key got to firing

A stop that is correct and never sooner

The combined stopping rule for bidirectional A* under a shared potential, measured against the sum rule alone on forty weighted grids — with the two frontiers' own keys traced expansion by expansion, the bookkeeping priced in work and in queue entries, and the alternation swept to find where the second rule could fire at all.

 0396,049792,0981,188,1481,584,1970326496128queries answeredcounted work, cumulativebreak-even at 2.7 queriesBellman–Ford from each sourceone reweighting, then Dijkstra256 vertices, 2,009 arcsanswers compared entry by entry

How long a reweighting stays true

Single-source shortest-path queries on graphs with negative arcs, priced as Bellman–Ford per query against one stored reweighting and Dijkstra — with the break-even query count swept against density, and the stored potential's survival measured against the share of arcs whose costs change between queries.

 00.50011.50arcs redrawn between queriesstored potential ÷ Bellman–Ford per query0.02%0.1%0.5%2%5%20%recomputed from nothingmended from the broken arcs256 vertices, 128 queriesarc costs redrawn

A potential mended where it broke

Johnson's stored potential under updates, repaired by a queue-driven relaxation from the broken arcs instead of recomputed from the virtual source: the total work against Bellman–Ford per query as arcs are redrawn, the relaxations a repair makes, how many vertices it changes, and the same three measurements when whole vertices' hidden potentials move.

All essays