A* Search

A\* is Dijkstra with a sense of direction. Dijkstra spreads outward evenly because it only knows the cost *behind* it. A\* adds a guess of the cost *ahead* — a heuristic — and uses it to lean the search toward the goal, so it explores far fewer nodes while still returning a genuine shortest path.

g, h, and f

1. 1g(n) — the real cost of the best path found so far from the start to node n.
2. 2h(n) — the heuristic: a cheap estimate of the remaining cost from n to the goal (on a map, often straight-line distance).
3. 3f(n) = g(n) + h(n) — the estimated total cost of a path *through* n. A\* always expands the frontier node with the smallest `f`.

Set h to zero everywhere and f becomes just g — A\* collapses back into Dijkstra. The heuristic is the only thing steering the search; the better the estimate, the more directly A\* drives at the goal.

// f = g + h; the priority queue is ordered by f
function astar(start, goal, neighbors, h) {
  const g = { [start]: 0 };
  const open = new MinHeap();          // ordered by f = g + h
  open.push(start, h(start));
  while (!open.empty()) {
    const u = open.pop();              // smallest f
    if (u === goal) return g[goal];
    for (const [v, w] of neighbors(u)) {
      const tentative = g[u] + w;      // candidate g for v
      if (tentative < (g[v] ?? Infinity)) {
        g[v] = tentative;
        open.push(v, tentative + h(v)); // priority = f
      }
    }
  }
  return Infinity; // unreachable
}