A* Search Algorithm

See how the heuristic guides A* toward the goal, exploring fewer nodes than Dijkstra

f(n) = g(n) + h(n)
g(n) = actual cost from start to n  |  h(n) = heuristic estimate from n to goal  |  f(n) = total estimated cost
Speed: 700ms
Unvisited
Current node
Exploring edge
Updated
Visited
Goal
Press Step or Play to begin A* from node A toward the goal

A* Tracking Table — g(n) + h(n) = f(n)

How A* Search Works

A* is an informed search algorithm that combines the actual distance travelled so far with an estimated remaining distance to decide which node to explore next.

set g[source] = 0, f[source] = h(source), all others = ∞
while there are unvisited nodes with finite f:
  current = unvisited node with smallest f(n) = g(n) + h(n)
  if current == goal: STOP // shortest path found!
  mark current as visited
  for each unvisited neighbour of current:
    newG = g[current] + edge weight
    if newG < g[neighbour]:
      g[neighbour] = newG
      f[neighbour] = newG + h(neighbour) // update total estimate
      previous[neighbour] = current

The heuristic h(n) estimates the remaining cost from node n to the goal. It must be admissible — it must never overestimate the true remaining distance. If it does, A* might miss the optimal path. Common admissible heuristics include straight-line (Euclidean) distance and Manhattan distance.

Why does A* explore fewer nodes? Dijkstra picks the node with the lowest g(n) — distance from the start. A* picks the node with the lowest f(n) = g(n) + h(n), which factors in how close a node is to the goal. This steers the search in the right direction, skipping nodes that are far from the goal. A* also stops as soon as the goal is reached, while Dijkstra must visit every node.

Special case: If h(n) = 0 for all nodes, the heuristic gives no guidance and A* degrades to Dijkstra exactly.

Dijkstra

Explores all directions equally. Picks the node with the smallest g(n). Must visit every reachable node. No knowledge of where the goal is.

A* Search

Explores toward the goal. Picks the node with the smallest f(n) = g(n) + h(n). Stops when the goal is reached. Uses a heuristic to skip irrelevant nodes.