Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Give the start node a cost of 0 and estimate its distance to the goal.
  2. Take the frontier node with the smallest f = g + h.
  3. If it is the goal, stop — its cost cannot be improved.
  4. Otherwise settle it and look at each neighbour.
  5. If reaching a neighbour this way is cheaper than any route found so far, record it and queue it with its own f.
  6. Repeat until the goal is settled or the frontier empties.

Key concepts

  • f = g + h: cost so far plus estimate remaining
  • Admissible heuristic — never overestimates — keeps the result optimal
  • With h = 0 it is exactly Dijkstra
  • A better heuristic expands fewer nodes, never a different answer

When to use it

Pathfinding where you know roughly which direction the goal lies — maps, grids, games. On graphs with no usable estimate, Dijkstra is the same algorithm without the overhead.

Did you know

A* was published in 1968 for Shakey, a robot at Stanford that needed to plan routes across rooms.