A* search algorithm

A*, pronounced “A-star,” is a graph traversal and pathfinding algorithm that finds the lowest-cost path between two nodes in a weighted graph. It searches outward from a starting node, but unlike an uninformed search, it uses an estimate of the remaining distance to steer toward the goal and explore far fewer nodes along the way.

A* ranks each candidate node by the function f(n) = g(n) + h(n), the sum of two costs:

  • g(n) is the actual cost of the path already traveled from the start to node n.
  • h(n) is a heuristic estimate of the cost still remaining from n to the goal.

The algorithm keeps its frontier of unexplored nodes in a priority queue ordered by f(n) and always expands the one with the lowest value. The heuristic is what makes the search both fast and correct. As long as h never overestimates the true remaining cost, a property called admissibility, A* is guaranteed to return an optimal path.

A* generalizes two simpler strategies. Setting h(n) to zero reduces it to Dijkstra’s algorithm, which weighs only the distance already covered, while dropping g(n) yields greedy best-first search, which runs faster but can settle for a longer route. Its main practical limitation is memory, because the frontier can grow exponentially with search depth, a cost measured as space complexity.

Drag the strategy slider in the explorer below to sweep between these three searches on the same grid and compare how many cells each one expands and the length of the route it returns.

Interactive diagram — enable JavaScript to view.
Build a Maze Solver in Python Using Graphs

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated July 28, 2026
Computer Science Glossary Share Feedback