vizlearn

A* Algorithm

Algorithms & Data StructuresBy Updated

Interactive pathfinding visualization. Click and drag on the grid to create barriers.

Toolbox

Execution Speed

Search Space

Status: Ready

Performance

Nodes Explored 0
Path Length 0
Total Cost 0.00

Legend

Open List
Closed List
Path

Overview

Dijkstra’s algorithm expands outward from the source in rings of equal cost. If the goal is due east, it still explores just as far north, south and west before reaching it. On a large map that is enormous wasted effort. The algorithm has no idea where it is going.

The problem with searching in every direction

A* adds that idea.

f = g + h

Every node carries three numbers:

  • g(n) — the actual cost of the best known path from the start to n. This is exactly Dijkstra’s distance.
  • h(n) — the heuristic: an estimate of the left cost from n to the goal.
  • f(n) = g(n) + h(n) — the estimated total cost of a route through n.

A* is then exactly Dijkstra with the priority queue ordered by f instead of g. Set h(n) = 0 everywhere and you get Dijkstra back exactly — A* is a strict extension, not a different algorithm.

Admissible, steady, and why it stays best

A heuristic is admissible if it never overestimates the true left cost. That single property is what guarantees A* finds a best path.

The reason: if h never overestimates, then f(n) never overestimates the cost of the best route through n. So when the goal is popped with total cost f, no unexplored node can be hiding a cheaper route. Any such node would have had a smaller f and been popped first.

Overestimate, and that breaks. An inflated h can make the true best route look worse than a bad one, and A* will return the bad one. The common heuristics on a grid are admissible by construction:

  • Manhattan |dx| + |dy| — admissible when movement is 4-directional, because that is the exact distance with no obstacles.
  • Euclidean √(dx² + dy²) — admissible always. Since a straight line is the shortest doable route, but weak (too low) on 4-directional grids.
  • Zero — admissible and useless: this is Dijkstra.

Note that Manhattan is not admissible if diagonal movement is allowed, because the diagonal route is shorter than |dx| + |dy|. That mismatch is the most common way people accidentally break optimality.

Choosing the heuristic is the whole design

The heuristic decides how much better than Dijkstra A* is, and getting it wrong is the usual failure.

Too weak (close to 0) and A* degenerates towards Dijkstra, exploring almost all of it.

Not admissible and the result is suboptimal. The classic mistake on a 4-directional grid is using Euclidean distance: it underestimates correctly. So it is admissible. But Manhattan distance is a tighter underestimate and so explores far less. Conversely, using Manhattan distance when diagonal movement is allowed overestimates and breaks optimality.

Too expensive to compute and the per-node saving is lost. h is evaluated for every node examined.

The practical rule: use the tightest admissible estimate that is cheap to compute, and match it to the actual movement rules.

For road networks the straight-line distance is admissible but weak, because roads are not straight. Production routing engines use landmark-based heuristics: precompute distances from a few hundred landmark nodes, and use the triangle inequality to derive much tighter bounds. That is one of the techniques that makes continental route planning interactive.

Guided tests

  1. See the search become directional. Press Run Algorithm and watch the explored region. It stretches toward the goal rather than spreading in a circle — that elongation is h doing its job.
  2. Turn the heuristic off. Set Heuristic to the zero or Dijkstra option and press Reset Grid, then run again. The explored area balloons into an even blob. The path found is the same length; the work to find it is far greater.

Where it is used

  • Game pathfinding. The default algorithm for moving units around a map, often on a grid or navigation mesh.
  • Robotics. Motion planning over occupancy grids, often with variants handling smooth space.
  • Route planning. Real navigation systems use A* with landmark heuristics, or contraction hierarchies which precompute shortcuts.
  • Puzzle solving. Sliding tiles, Rubik's cube and similar. Where the heuristic is a relaxation of the puzzle. For the 15-puzzle, the sum of Manhattan distances of each tile from its home.
  • Word ladders and state-space search often, where the graph is made on demand.
  • Automated planning in AI, where the state space is enormous and heuristics are important.

The puzzle case illustrates a general technique for inventing heuristics: solve a relaxed version of the problem. Ignoring that tiles block each other gives the Manhattan-distance heuristic. This is admissible because the real puzzle can only be harder.

Sources and next steps

Run it in Python

The same grid solved twice: once by Dijkstra and once by A* with a Manhattan heuristic. Both find a shortest path; the interesting number is how many cells each one had to expand to do it.

a_star.pyPython 3
Output
How the code works
  1. heapq.heappush(heap, (tentative + h, h, nxt))The one line that separates A* from Dijkstra: the priority is f = g + h, cost already spent plus cost estimated to remain, instead of g alone.
  2. (f, h, cell)The second element breaks ties. On a grid where every step costs 1 an enormous number of cells share an f value, and preferring the one nearest the goal is what turns a fan into a beeline. It changes nothing about correctness and most of the measured saving here comes from it.
  3. search(lambda a, b: 0, "Dijkstra")With h = 0 the formula collapses to f = g, so the identical function is Dijkstra. That is the cleanest way to see that A* is a generalisation, not a different algorithm.
  4. def manhattan(a, b):Steps are up/down/left/right and each costs 1, so the Manhattan distance can never overestimate what remains. That property — admissibility — is what keeps the answer optimal.
  5. if tentative < g.get(nxt, float("inf")):Compares on g, never on f. The heuristic decides what to look at next; it must not be allowed to decide what the route actually cost.
  6. expandedThe number that matters. Both runs return a shortest path of the same length, and A* gets there having opened far fewer cells — on a game map or a road network that is the entire point.
Change one thing
  • Multiply the heuristic by 5. It is now inadmissible: expansions drop further, and the path it returns can be longer than the shortest one.
  • Swap Manhattan for Euclidean (math.hypot). Still admissible on this grid, but weaker, so more cells get expanded.
  • Wall the goal off completely. Both searches drain the heap and the reconstructed path is nonsense — a real implementation has to check that the goal was actually reached.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set Execution Speed to its minimum (1). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Setting the heuristic to zero turns A* into:
  2. An admissible heuristic is one that:
  3. Both searches in the program return a path of the same length. What differs?





 Cheat sheet
A* Pathfinding Algorithm
Watch A* combine real distance with a heuristic estimate to reach the goal while exploring far fewer nodes than Dijkstra.
ALGORITHMS · vizlearn.in/dsa/a_star.html
More in Algorithms
AlgorithmsMinimum Spanning TreeAlgorithmsTwo PointersAlgorithmsSliding WindowAlgorithmsGreedy Algorithms
Further reading
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact