A* Search Algorithm

Complexity (theory): depends on the heuristic; worst case exponential in the search depth, memory often the limit. Optimal when the heuristic is admissible. The counters above are measured for the graph shown.

What Is the A* Search Algorithm?

A* (pronounced “A star”) is a pathfinding and graph traversal algorithm. It finds a lowest-cost path from a start node to a goal node. It is like Dijkstra’s algorithm with a sense of direction: instead of expanding nodes only by the cost already paid, it also uses an estimate of the remaining cost.

For every node n, A* computes f(n) = g(n) + h(n). Here g(n) is the exact cost from the start to n, and h(n) is the heuristic, an estimate of the cheapest cost from n to the goal. A* always expands the open node with the smallest f.

How A* Search Works: Steps, Example and Code

Understanding the Heuristic

The heuristic decides how good A* is. A heuristic is admissible if it never overestimates the true remaining cost. With an admissible heuristic, A* returns an optimal path. A heuristic is consistent if h(n) is never more than the edge cost to a neighbor plus the neighbor’s h. Consistent heuristics are also admissible, and they guarantee that a node is never expanded twice.

• Euclidean distance (straight line): admissible when you can move in any direction. This visualization uses it, and edge weights are never smaller than the scaled straight-line distance.
• Manhattan distance: suits grids with four-direction movement.
• Chebyshev or octile distance: suits grids that allow diagonal moves.
• h = 0: A* behaves exactly like Dijkstra’s algorithm.
• Overestimating h: faster, but the path may no longer be optimal.

How the A* Algorithm Works Step by Step

1. Put the start node in the open set with g = 0 and f = h(start).
2. Remove the open node with the smallest f. This is the current node.
3. If it is the goal, rebuild the path from the parent links and stop.
4. Otherwise, move it to the closed set.
5. For each neighbor not in the closed set, compute the new g through the current node.
6. If the new g is better than the stored one, save it, set the parent, update f, and add the neighbor to the open set.
7. Repeat from step 2. If the open set becomes empty, there is no path.

A* Example With a Step-by-Step Walkthrough

Use edges S–A 1, S–B 4, A–B 2, A–C 5, B–G 5 and C–G 3, with the goal G. Straight-line estimates h are S 7, A 6, B 4, C 3 and G 0 (all admissible).

1. Open set: S with f = 0 + 7 = 7. Expand S. A gets g = 1, f = 1 + 6 = 7. B gets g = 4, f = 4 + 4 = 8.
2. Expand A (f = 7). Through A, B costs 1 + 2 = 3, which beats 4, so B now has f = 3 + 4 = 7. C gets g = 6, f = 6 + 3 = 9.
3. Expand B (f = 7). G gets g = 3 + 5 = 8, f = 8.
4. Expand G (f = 8). It is the goal.

The path is S → A → B → G with cost 8. Node C was never expanded. Dijkstra’s algorithm would expand C (its distance is 6, below the goal’s 8) before finishing, so A* did less work thanks to the heuristic.

A* Pseudocode

AStar(graph, start, goal, h):
  g[start] = 0
  open = { start }       // priority by f = g + h
  closed = { }
  while open is not empty:
    u = node in open with smallest g[u] + h(u)
    if u == goal: return path from start to goal
    remove u from open; add u to closed
    for each neighbor v of u with edge weight w:
      if v in closed: continue
      if g[u] + w < g[v]:
        g[v] = g[u] + w
        parent[v] = u
        add v to open
  return failure

A* Implementation in JavaScript

function aStar(graph, start, goal, h) {
  // graph: { S: [['A', 1], ['B', 4]], ... }  (neighbor, weight)
  const g = { [start]: 0 }, parent = {};
  const open = new Set([start]), closed = new Set();
  while (open.size) {
    let u = null;                                    // lowest f = g + h
    for (const n of open) if (u === null || g[n] + h(n) < g[u] + h(u)) u = n;
    if (u === goal) {
      const path = [];
      for (let x = goal; x !== undefined; x = parent[x]) path.unshift(x);
      return { path, cost: g[goal] };
    }
    open.delete(u);
    closed.add(u);
    for (const [v, w] of graph[u] || []) {
      if (closed.has(v)) continue;
      const tentative = g[u] + w;
      if (g[v] === undefined || tentative < g[v]) {
        g[v] = tentative;
        parent[v] = u;
        open.add(v);
      }
    }
  }
  return null;                                       // no path
}

This version scans the open set to find the best node, which is easy to read. Production code stores the open set in a binary heap. The closed-set skip is safe when the heuristic is consistent, as in this article and in the visualization.

A* Search Time and Space Complexity

Time and Space Complexity of A*

A*’s cost depends heavily on the heuristic. With a poor heuristic, it can expand almost every node, like Dijkstra’s algorithm. With a perfect heuristic, it expands only the nodes on the best path. In the worst case, the number of expanded nodes grows exponentially with the solution depth.

A* Search Advantages, Disadvantages and Comparisons

Advantages and Disadvantages of A*

Advantages: it is optimal with an admissible heuristic, it usually expands far fewer nodes than Dijkstra’s algorithm, and the heuristic can be tuned for each problem.

Disadvantages: it can use a lot of memory, it needs a good heuristic, and a bad heuristic (one that overestimates) can return a non-optimal path.

A* vs Dijkstra’s Algorithm

Using A* Search in Practice: Applications and Mistakes

Common Applications of A*

• Video game character and unit pathfinding.
• Robot navigation and motion planning.
• Route finding in maps.
• Puzzle solving, such as the sliding-tile puzzle.

Common Mistakes When Implementing A*

• Using a heuristic that overestimates, which breaks optimality.
• Using a heuristic in different units than the edge costs.
• Choosing a node by h alone, which turns it into greedy best-first search.
• Skipping parent updates when a cheaper route is found.
• Using a plain list instead of a heap for large maps.

A* Variations and Practical Tips

Many real systems use a tuned form of A*. These ideas show how the basic algorithm adapts.

Tie-Breaking on Grids

Grid maps often produce many nodes with the same f value. Preferring the node with the larger g, which is the one closer to the goal, usually reduces the number of expanded nodes without changing the path cost.

Weighted A*

Weighted A* uses f = g + w · h with w greater than 1. The search leans harder toward the goal and often finishes much faster. When h is admissible, the returned path costs at most w times the optimal cost, so you trade a bounded loss of quality for speed. Games often accept this trade.

Iterative Deepening A*

IDA* runs depth-first searches that stop when f exceeds a threshold, and then raises the threshold and repeats. It uses memory proportional to the path length instead of storing a large open set, but it may revisit nodes. It suits puzzles with huge state spaces.

Testing an A* Implementation

Because A* is only optimal with a good heuristic, testing has to cover the heuristic as well as the search.

Compare With Dijkstra’s Algorithm

For the same start and goal, A* with an admissible heuristic must return the same path cost as Dijkstra’s algorithm. If A* returns a higher cost, the heuristic overestimates somewhere.

Check That the Heuristic Is Admissible

Compute the true shortest distance from every node to the goal, for example by running Dijkstra’s algorithm from the goal on the reversed graph. Then confirm that h(n) is never larger than that true distance. In the visualization, each edge weight is at least the straight-line distance between its nodes divided by 40, so the straight-line heuristic is safe.

Edge Cases to Try

• A start node equal to the goal, which should return a one-node path with cost 0.
• A goal that cannot be reached, which should return no path.
• A graph where the heuristic is 0 everywhere, which should behave like Dijkstra’s algorithm.
• Two equally cheap paths, where either path is correct.

Frequently Asked Questions About A*

What is A* in simple words?

It is a pathfinding algorithm that picks the next node by cost so far plus an estimate of the cost remaining.

What does f = g + h mean?

g is the cost from the start, h is the estimated cost to the goal, and f is their sum, the estimated total cost through that node.

What is an admissible heuristic?

One that never overestimates the true remaining cost.

Is A* always optimal?

Yes when the heuristic is admissible. With a non-admissible heuristic, it may not be.

How is A* different from Dijkstra?

A* uses a heuristic to focus on the goal, while Dijkstra expands by cost so far only.

What happens if h is 0?

A* becomes Dijkstra’s algorithm.

Which heuristic should I use on a grid?

Manhattan distance for four-direction moves, and octile or Chebyshev distance when diagonal moves are allowed.

Conclusion

A* expands nodes by f = g + h, so it moves toward the goal while still tracking the real cost. With an admissible heuristic, it finds optimal paths, often expanding fewer nodes than Dijkstra’s algorithm. Try several start and goal pairs in the visualization and watch the f values on the nodes.