Dijkstra's algorithm is thorough but incurious: its
priority queue orders cells purely by accumulated cost g(n), so it expands outward in
every direction at once with no notion of which way the goal actually is. A* keeps Dijkstra's exact
machinery — a priority queue, relax-and-push, finalize-on-pop — but reorders the queue by
f(n) = g(n) + h(n) instead, where h(n) is a heuristic
estimate of the remaining cost from n to the goal. Cells that merely look close to the
goal now cut ahead of cells that are just cheap so far, and the search visibly leans toward the
target instead of flooding outward evenly.
Same grid, same terrain, same start and end cells as the Dijkstra page — click a cell to cycle
its cost through 1 → 3 → 9, so the two demos stay directly comparable. The
heuristic here is Manhattan distance to the goal (the grid only allows
up/down/left/right moves, so that's the fewest steps physically possible, and every step costs at
least 1). Step through and watch the queue: each chip now shows g (cost so far),
h (heuristic estimate), and f (their sum, what the queue actually sorts
by) — and the running visited-count at the end tells you how much less ground A* covered than
Dijkstra did on the exact same grid. Switch the heuristic mode to inflated to see
what happens when h is allowed to overestimate: still fast, and on this particular
terrain still correct — but not for a reason you should trust in general. See Pitfalls below for a
grid where inflating h actually returns the wrong answer.
Dijkstra's correctness rests on one invariant: whenever a cell is popped, its known distance is
already optimal, because the queue always hands back whichever unfinished cell is globally
cheapest so far. A* preserves exactly this invariant under one extra condition on the heuristic,
called admissibility: h(n) must never overestimate the true remaining
cost from n to the goal. When that holds, f(n) = g(n) + h(n) is a lower
bound on the true cost of the cheapest path that passes through n — so a cell with a
lower f can never be beaten by a cell with a higher one once both their true costs are
known, and the "pop it, it's final" argument still goes through. Manhattan distance is admissible
here because it's a hard floor: no path can physically take fewer steps than the straight-line grid
distance, and no step costs less than 1, so h(n) can never claim more remaining cost
than the graph is capable of actually charging.
What admissibility buys is focus, not a different answer. A heuristic of exactly zero everywhere is trivially admissible (it never overestimates a non-negative true cost) and turns A* back into plain Dijkstra — no wasted exploration in the wrong direction, but no bias toward the goal either. A good admissible heuristic sits as close to the true remaining cost as it can without ever exceeding it: tight enough to steer the queue, never so tight it lies.
Identical to the Dijkstra reference implementation with one change: the priority queue orders by
f = g + h instead of by g alone, and each push computes the heuristic for
the newly-relaxed cell.
function aStar(grid, rows, cols, start, end) {
const key = (r, c) => r * cols + c;
const n = rows * cols;
const [er, ec] = end;
const h = (r, c) => Math.abs(r - er) + Math.abs(c - ec); // Manhattan distance, admissible here
const g = new Array(n).fill(Infinity);
const visited = new Array(n).fill(false);
const parent = new Array(n).fill(-1);
const startK = key(...start), endK = key(...end);
g[startK] = 0;
// [f, g, cellKey] triples — same array-backed queue as Dijkstra, just sorted by f now.
const pq = [[h(start[0], start[1]), 0, startK]];
while (pq.length) {
let mi = 0;
for (let i = 1; i < pq.length; i++) if (pq[i][0] < pq[mi][0]) mi = i;
const [, d, cur] = pq.splice(mi, 1)[0];
if (visited[cur]) continue; // stale entry, already finalized cheaper
visited[cur] = true;
if (cur === endK) break;
const r = Math.floor(cur / cols), c = cur % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (visited[nk]) continue;
const ng = d + grid[nk];
if (ng < g[nk]) {
g[nk] = ng;
parent[nk] = cur;
pq.push([ng + h(nr, nc), ng, nk]);
}
}
}
if (!visited[endK]) return null;
const path = [];
for (let cur = endK; cur !== -1; cur = parent[cur]) path.push(cur);
return { path: path.reverse(), cost: g[endK] };
}An inadmissible heuristic can return the wrong answer outright — not just
explore inefficiently, actually report a path that costs more than the cheapest one. Once
h can overestimate, f(n) is no longer a reliable lower bound, so a cell
on the true cheapest path can be shelved behind a cell that only looks closer to the goal,
and finish first without the real winner ever getting a chance to be compared. Here's a small grid,
worked out and checked against Dijkstra, where inflating the heuristic to 2× Manhattan
distance does exactly that:
3 3 9 1 1
3 1 1 1 1
1 1 1 3 1
1 1 1 9 1Start top-left, end bottom-right. The true cheapest path costs 9: down the left
column once, then straight across row 1, then down to the corner. With h inflated to
2× Manhattan distance, A* instead commits to cutting across row 2 — it costs
11, 22% more than optimal, and the algorithm reports it as if it were the
answer, with no indication anything went wrong. The default terrain in the demo above happens not
to expose this — its cost structure is uniform enough by column that even a heavily inflated
heuristic still lands on an optimal path, just faster — which is itself worth noticing: an
inadmissible heuristic can seem to work correctly for a long time before the terrain finally proves
it wrong. Admissibility isn't optional insurance against a rare edge case; it's the entire basis for
trusting the answer at all.
The heuristic has to be reachable to compute cheaply, or it defeats the point. Manhattan distance is O(1) per cell precisely because it ignores the terrain — it's a lower bound on the best possible case, not a prediction of the actual cost. A heuristic that tried to account for terrain (say, by running a smaller search of its own) could be tighter and admissible, but spending significant work per cell to estimate remaining cost undermines the reason to prefer A* over Dijkstra in the first place.
It's still single-source, single-target. Same limitation as Dijkstra: one run finds the cheapest path between exactly the start and end cells given, not between every pair. Different heuristics can be swapped in per problem, but the algorithm doesn't generalize to all-pairs the way Floyd-Warshall does.
Time: O((V + E) log V) with a binary-heap priority queue — same
bound as Dijkstra, since in the worst case (a heuristic of zero everywhere) A* degenerates to
exactly Dijkstra and explores just as much. The heuristic changes how much of that worst case is
actually paid in practice, not the asymptotic ceiling: a good admissible heuristic prunes the
search space without changing what the algorithm is allowed to cost when the heuristic gives it no
useful information. The array-backed queue in the demo and reference code above is
O(V² + E), same as Dijkstra's, for the same reason (linear-scan extraction).
Space: O(V) for the cost array, parent array, and queue — identical
to Dijkstra, plus O(1) per cell to compute Manhattan distance on demand rather than storing it.
For a decision guide across all eleven of this site's shortest-path entries — including exactly when a heuristic is worth having at all — see Choosing a Shortest-Path Algorithm.