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

Invariant — where it appears

A property an algorithm's state satisfies at every step, stated so that it can be checked rather than believed. The two here are load-bearing: the intervals of a bidirectional search have equal width, and a listing walk finishes everything to its left before it starts.

Named by 6 essays across 4 fields — each of them below, with the objects they name alongside it.

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

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.

graphs · Graph 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

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.

graphs · Graph probe 1: 0–1 absent9 still to ask10 of 10 as good as anyprobe 2: 0–2 absent8 still to ask9 of 9 as good as anyprobe 3: 0–3 absent7 still to ask8 of 8 as good as anyprobe 4: 0–4 present6 still to ask7 of 7 as good as anyprobe 5: 1–2 absent5 still to ask6 of 6 as good as anyprobe 6: 1–3 absent4 still to ask5 of 5 as good as anyprobe 7: 1–4 present3 still to ask4 of 4 as good as anyprobe 8: 2–3 absent2 still to ask3 of 3 as good as anyprobe 9: 2–4 present1 still to ask2 of 2 as good as anyprobe 10: 3–4 absentdecided1 of 1 as good as any5 vertices · 10 pairs · 59,049 states solvedsolid: present · dotted: absent · coloured: this probe

Every pair must be asked

Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.

floors · Floor forward · wavelet tree18,377forward · rank directories5,037forward · C table100forward · sample marks8,193forward · sampled positions3,598reverse · wavelet tree18,377reverse · rank directories5,037reverse · C table100reverse · sample marks8,193droppedreverse · sampled positions3,598dropped8,192 characters · sampling every 3216.7% of both halves

The half that is never asked where

A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.

indexes · Distance range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps

The array the walk never reads

Document listing compares a chain entry against the start of a range. The comparison is true exactly when the document has not been reported yet — which the walk already knows, because it just wrote it down.

indexes · Index range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps

A document already in the answer

The same walk, with the chain's test replaced by a lookup in the answer so far. It reports the same documents at the same cost, and two exchanged lines make it lose nine of seventeen without failing.

structures · Index

Named alongside it

The objects these essays reach for when they reach for this one.

Index sizeCheckCorrectnessCounterexampleDijkstra's algorithmDocument arrayDocument listingHeuristic searchOutput-sensitivePrevious occurrence chainRange minimumShortest path

All concepts