A* search only pays off when there's a cheap, admissible estimate of the remaining distance — on the grid A*'s own page uses, that's Manhattan distance, which works because the grid has coordinates and cost correlates with physical distance. Plenty of real graphs have neither: a citation graph, a task-dependency graph, a network where the edge weight is a toll or a latency with no embedding behind it at all. The ALT algorithm (Goldberg & Harrelson, 2005 — A*, Landmarks, Triangle inequality) builds an admissible heuristic from nothing but the graph's own edge weights: pick a handful of landmark nodes, run one Dijkstra pass from each — in both directions — and the triangle inequality alone turns those precomputed distances into a valid lower bound to any goal, for any start, with no coordinates anywhere in the calculation.
Seven nodes, thirteen directed edges, one landmark (★A) — positions on the canvas
below are for layout only and carry no meaning; unlike the Dijkstra/A* grid, dragging a node here
wouldn't change a single edge weight. The panel above the graph is preprocessing: two
one-time Dijkstra runs from A, computed once at page load and reused for every query below — forward
(d(A, x), A's own outgoing distances) and backward (d(x, A), via Dijkstra on
the reversed graph). Pick a query and a heuristic mode, then step through: ALT uses
h(v) = max(0, d(A,goal) − d(A,v), d(v,A) − d(goal,A)); none zeroes the
heuristic out, which is exactly plain Dijkstra. Watch the visited-count line at the end — same
answer, every time, just less work to get there.
For any landmark L and any pair of nodes v, t, the triangle
inequality gives two separate facts for free, just from L's own precomputed distances.
First: d(L, v) + d(v, t) ≥ d(L, t), because going straight from L to
t can never cost more than detouring through v — rearranged, that's
d(v, t) ≥ d(L, t) − d(L, v), a lower bound built entirely from L's
forward distances. Second, running the same argument on the reversed graph:
d(v, t) + d(t, L) ≥ d(v, L), giving d(v, t) ≥ d(v, L) − d(t, L), a lower
bound built from L's backward distances (distance to L,
not from it — the two only coincide if the graph happens to be undirected). Either fact alone is a
valid, safely-below-the-truth estimate of the remaining distance from v to the goal
t; taking the max of both (and of every landmark's own pair of bounds, with more than
one landmark) only tightens the bound; clamping below at 0 keeps it from ever going negative. That
max is exactly h(v), and because every ingredient is a real shortest-distance value
computed by an already-correct Dijkstra run, admissibility isn't an assumption that needs checking
per graph the way a hand-picked coordinate heuristic would — it's a direct consequence of the
triangle inequality, true for any landmark, any graph, any weights, as long as every edge weight is
non-negative (Dijkstra's own precondition, inherited unchanged).
The preprocessing and the query are genuinely separate phases. Computing d(A, x) and
d(x, A) for every x costs two full Dijkstra runs, done once, no matter which
goal a later query asks about — the same landmark table answers a query to any node in the graph.
That's the trade A* itself can't offer with a coordinate heuristic: Manhattan distance is free to
compute per cell precisely because it needs no preprocessing at all, but it's only available when
coordinates exist in the first place. ALT spends real, upfront work to manufacture a heuristic where
none was otherwise available, and gets it back across every query that reuses the same table.
Preprocessing is two Dijkstra runs per landmark — one on the graph, one on the graph with every edge reversed. The search itself is exactly A*'s own reference implementation, unchanged, just handed this heuristic instead of Manhattan distance:
function dijkstra(numNodes, adj, src) {
const dist = new Array(numNodes).fill(Infinity);
const visited = new Array(numNodes).fill(false);
dist[src] = 0;
for (let iter = 0; iter < numNodes; iter++) {
let u = -1, best = Infinity;
for (let i = 0; i < numNodes; i++) if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; }
if (u === -1) break;
visited[u] = true;
for (const [v, w] of adj[u]) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
}
return dist;
}
function reverseAdj(numNodes, adj) {
const radj = Array.from({ length: numNodes }, () => []);
for (let u = 0; u < numNodes; u++) for (const [v, w] of adj[u]) radj[v].push([u, w]);
return radj;
}
// preprocessing: once per landmark, reused by every later query
function precomputeLandmark(numNodes, adj, landmark) {
const forward = dijkstra(numNodes, adj, landmark); // d(landmark, x)
const backward = dijkstra(numNodes, reverseAdj(numNodes, adj), landmark); // d(x, landmark)
return { forward, backward };
}
// query time: with k landmarks, take the max bound across all of them —
// a max of several individually-valid lower bounds is still a valid lower bound.
function landmarkHeuristic(landmarks, goal) {
return function h(node) {
let best = 0;
for (const { forward, backward } of landmarks) {
best = Math.max(best, forward[goal] - forward[node], backward[node] - backward[goal]);
}
return best;
};
}
// A* itself is unmodified from here — see the A* page's reference implementation,
// called with h = landmarkHeuristic(landmarks, goal) in place of Manhattan distance.Treating a directed graph as if it were symmetric silently breaks admissibility.
The backward bound needs d(v, L) — the distance from v
to the landmark — which is a different number from d(L, v) whenever the graph
is directed. A version that skips the second Dijkstra run and reuses the forward table for both
bounds looks like a reasonable shortcut (half the preprocessing, and it's still just subtracting two
numbers), but it substitutes a number that was never a valid backward distance in the first place. On
this page's own seven-node graph, that substitution gets the right answer on 27 of the 30 reachable
ordered pairs from landmark A by accident — the wrong 3 include start D, goal
E, where the correct heuristic (and plain Dijkstra) both agree the cheapest path costs
7, and the symmetric-shortcut heuristic reports 23 — 229% more
expensive than optimal, with no indication anything went wrong. Both Dijkstra runs are required
for a directed graph, full stop; only an undirected graph gets to skip the second one, because there
d(v, L) and d(L, v) are the same value by definition.
The preprocessing cost is real, and it only pays for itself across repeated queries.
On this same graph, averaged across all 30 reachable ordered pairs, ALT visits 3.55 nodes per query
against plain Dijkstra's 4.50 — a real reduction, but well under one node's worth of work saved per
query, while the one-time preprocessing already spent two full Dijkstra traversals computing the
landmark table in the first place. A single one-off query is cheaper run as plain Dijkstra outright;
ALT wins specifically when the same table answers many queries against different goals, the way a
route planner precomputes once and serves years of trip requests. Landmark placement matters too and
isn't built into this demo's fixed single-landmark setup — trying each of this graph's seven nodes as
the sole landmark swings the average visited-count reduction from 15.3% to 23.8% depending which one
is picked, before any query ever runs; the standard practical fix is choosing landmarks far apart from
each other (a farthest-first placement), not arbitrarily, and using several of them at once via the
max in landmarkHeuristic above.
Time: preprocessing costs O(k · (V + E) log V) for k
landmarks with a binary heap — two Dijkstra runs each, forward and backward — done once and reused by
every subsequent query. Each query after that is exactly A*'s own bound, O((V + E) log V)
worst case, typically less in practice as the heuristic prunes the search; a heuristic of zero
everywhere (no landmarks, or every landmark equally uninformative for this particular pair) degrades
to plain Dijkstra, never worse. The array-backed Dijkstra in the demo and reference code above is
O(V² + E) per run instead, the same array-vs-heap trade
Dijkstra's own page makes for its demo.
Space: O(k · V) for the landmark distance tables — two arrays of length
V per landmark — plus A*'s own O(V) for the cost array, parent array, and
queue during a query.
For a decision guide across all eleven of this site's single-cheapest-path entries — including exactly when a landmark-built heuristic is worth the preprocessing over Dijkstra's zero-setup default — see Choosing a Shortest-Path Algorithm.