g + h: known cost plus estimated cost
For each vertex n, A* tracks two numbers:
- g(n) — the actual cost of the best path found so far from
the start to n (this is the number Dijkstra uses);
- h(n) — a heuristic estimate of the cost still to
go from n to the goal (e.g. straight-line distance on a map).
It always expands the vertex with the smallest total,
f(n) = g(n) + h(n),
— "cost already spent, plus a guess of what's left." A vertex that is close to the start but
pointing away from the goal has a big h, so A* leaves it alone and chases
the promising ones instead. It reads the smallest f from a
priority queue,
exactly like fast Dijkstra.
// A tiny weighted graph. h[] is a heuristic estimate of the remaining cost to the goal "G".
const adj: Record<string, [string, number][]> = {
S: [["A", 1], ["B", 4]],
A: [["B", 1], ["G", 5]],
B: [["G", 2]],
G: [],
};
const h: Record<string, number> = { S: 5, A: 3, B: 2, G: 0 };
const start = "S", goal = "G";
const g: Record<string, number> = { S: 0 };
const cameFrom: Record<string, string> = {};
const open = new Set<string>([start]);
while (open.size > 0) {
// Pick the open node with the smallest f = g + h.
let current = "";
let bestF = Infinity;
for (const n of open) {
const f = g[n] + h[n];
if (f < bestF) { bestF = f; current = n; }
}
if (current === goal) break;
open.delete(current);
for (const [next, w] of adj[current]) {
const tentative = g[current] + w;
if (tentative < (g[next] ?? Infinity)) {
g[next] = tentative;
cameFrom[next] = current;
open.add(next);
}
}
}
// Rebuild the path backwards from the goal.
const path: string[] = [goal];
let node = goal;
while (node !== start) { node = cameFrom[node]; path.unshift(node); }
console.log("path:", path.join(" -> "));
console.log("cost:", g[goal]);
A* threads straight to S \to A \to B \to G at cost
4, guided by h instead of exploring the whole
graph.
When is A* guaranteed correct?
The heuristic has one job: never overestimate the true remaining cost. Such a
heuristic is called admissible. As long as h never
claims the goal is farther than it really is, A* is guaranteed to return the genuine shortest path
— while still exploring far fewer vertices than Dijkstra.
- Expands vertices by smallest f(n) = g(n) + h(n).
- With an admissible heuristic (never overestimates), A* finds the
optimal path.
- With h(n) = 0 everywhere, A* is Dijkstra.
In a game, an enemy chasing you across a grid uses A* with h set to the
straight-line (or "as-the-crow-flies") distance to your position — admissible, because a real path
around walls can only be longer than the straight line, never shorter. The result is a
search that hugs the direct route and ignores the far corners of the map, so it's fast enough to
run for dozens of characters every frame. Route planners do the same across road networks.
-
If the heuristic overestimates (claims the goal is farther than it is), A* can
return a sub-optimal path — it may be faster, but you lose the shortest-path guarantee.
-
h estimates the distance to the goal, not from the
start. Mixing up g and h breaks the search.
-
A heuristic of 0 is admissible but useless — it gives you plain
Dijkstra with no steering.