Virtual Lab
Log InSign Up

A* (A-Star) Algorithm Simulator: Interactive Visualization with Heuristics

A* expands the node with the smallest f(n) = g(n) + h(n): the cost already paid plus the estimated cost remaining. If h never over-estimates (it is admissible), A* finds the cheapest path while exploring far fewer nodes than uniform-cost search.

About this visualization

A* expands the node with the smallest f(n) = g(n) + h(n): the cost already paid plus an estimate of the cost remaining. With an admissible heuristic it finds the cheapest path while exploring far fewer nodes than uniform-cost search. Build any graph, set h, and watch f values decide the order.

How it works

  1. g(n) is the real cost from the start; h(n) is the estimated cost to the goal.
  2. Expand the frontier node with the smallest f = g + h.
  3. If a cheaper path to a known node appears, update it (and re-open it if it was already expanded).

Formulas used

  • f(n)=g(n)+h(n)f(n) = g(n) + h(n)
  • Admissible: h(n)≤h∗(n)h(n) \le h^{*}(n), the true cost to the goal
  • Consistent: h(n)≤c(n,m)+h(m)h(n) \le c(n, m) + h(m)

Worked example

On the Romania map from Arad to Bucharest with straight-line distances as h, A* expands Arad (f = 366), Sibiu (393), Rimnicu (413), Fagaras (415) and Pitesti (417), then picks Bucharest (f = 418) via Arad → Sibiu → Rimnicu → Pitesti → Bucharest. That is the optimal path, found with 5 expansions where uniform-cost search needs 12.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Worst caseExponential in the heuristic's error
SpaceO(bd)O(b^{d})

Complete. Optimal when h is admissible (and consistent for graph search). The better h is, the fewer nodes are expanded.

When to use it

  • Route planning in maps, games and robotics.
  • Learning admissible and consistent heuristics.
  • Comparing A* with Dijkstra and greedy search.

Frequently asked questions

What does an admissible heuristic mean?

h(n) never over-estimates the true cost from n to the goal. With an admissible heuristic A* is guaranteed to find an optimal path.

Is A* better than Dijkstra's algorithm?

With a good heuristic A* explores far fewer nodes. With h = 0 it becomes uniform-cost search (Dijkstra).

What is the time complexity of A*?

It is exponential in the worst case, but practical performance depends on how accurate the heuristic is. It keeps all generated nodes in memory, O(bd)O(b^{d}).

What is a consistent heuristic?

h(n) ≤ cost(n, m) + h(m) for every edge n → m. Consistency implies admissibility and means A* never needs to re-open nodes.