A* Algorithm

Combining Distance and Direction

Dijkstra's algorithm finds the shortest path, but it explores blindly—expanding outward in all directions like ripples in a pond. What if we could give it a sense of direction? What if we could tell it: "The goal is over there"?

This is exactly what A* (pronounced "A-star") does. It combines the proven optimality of Dijkstra with the efficiency of goal-directed search.

The magic formula is deceptively simple:

Let's unpack each term:

• $g(n)$ is the actual cost from the start to node $n$. This is what Dijkstra uses—the distance we've measured by actually traversing the graph.
• $h(n)$ is the estimated cost from $n$ to the goal. This is the heuristic—our best guess at how far we still need to go.
• $f(n)$ is the total estimated cost of the cheapest path through $n$. We prioritize exploring nodes with the lowest $f(n)$.

Think of it this way: $g(n)$ tells us what we know (how far we've come), and $h(n)$ tells us what we believe (how far we have to go). Together, they guide us toward the goal while still ensuring we find the optimal path.

A* is Dijkstra with a sense of direction.

Why This Works

Consider how Dijkstra expands its search. Starting from the origin, it explores all nodes at distance 1, then all nodes at distance 2, and so on. The frontier forms concentric circles around the start—expanding uniformly in every direction, even directions that lead away from the goal.

A* changes this by biasing the search toward the goal. Instead of expanding in perfect circles, A* stretches its frontier into an ellipse oriented toward the destination. Nodes that are both close to the start and close to the goal get explored first.

Watch how Dijkstra's frontier expands as a circle while A*'s frontier stretches toward the goal. This focused exploration is why A* often visits far fewer nodes.

The key insight is that the heuristic $h(n)$ pulls the search toward the goal without sacrificing correctness. As long as the heuristic never overestimates the true cost (we call this admissible), A* will always find the optimal path.

A* in Action

Let's watch A* navigate through a grid with obstacles. Notice how it explores nodes preferentially in the direction of the goal, while still considering the actual distances traveled.

Click on any cell to see its $f$, $g$, and $h$ values. The priority queue orders cells by their $f$ value—lower $f$ means the cell gets explored sooner.

Pay attention to the frontier shape. Unlike BFS or Dijkstra, A*'s frontier isn't symmetric. It bulges toward the goal, exploring the most promising paths first.

Understanding F, G, and H

Each cell in an A* search carries three values. Understanding what each one means is crucial for intuition.

• g (green): The shortest known distance from the start. This is measured, not estimated.
• h (blue): The heuristic estimate to the goal. With Manhattan distance, this is $|x_1 - x_2| + |y_1 - y_2|$.
• f (purple): The sum $g + h$. Cells with lower $f$ are explored first.

Notice how cells near the start have low $g$ but high $h$, while cells near the goal have high $g$ but low $h$. The cells along the optimal path tend to have the lowest $f$ values.

A* vs Dijkstra: The Showdown

How much difference does that heuristic make? Let's find out by running both algorithms side-by-side on terrain with varying costs.

Both algorithms find the same optimal path—that's guaranteed when the heuristic is admissible. But look at the node counts. A* typically explores far fewer cells because it doesn't waste time searching in the wrong direction.

This is the power of informed search. By incorporating knowledge about where we want to go, we can dramatically reduce the work needed to get there.

The Algorithm

Here is A* in pseudocode:

A*(graph, start, goal, heuristic):
    open_set ← priority queue ordered by f(n)
    closed_set ← empty set
    g_score ← map with default value ∞
    parent ← empty map
    
    g_score[start] ← 0
    f_score[start] ← heuristic(start, goal)
    add start to open_set with priority f_score[start]
    parent[start] ← null
    
    while open_set is not empty:
        current ← extract node with lowest f from open_set
        
        if current = goal:
            return reconstruct_path(parent, goal)
        
        add current to closed_set
        
        for each neighbor of current:
            if neighbor in closed_set:
                continue
            
            tentative_g ← g_score[current] + cost(current, neighbor)
            
            if tentative_g < g_score[neighbor]:
                parent[neighbor] ← current
                g_score[neighbor] ← tentative_g
                f_score[neighbor] ← tentative_g + heuristic(neighbor, goal)
                
                if neighbor not in open_set:
                    add neighbor to open_set with priority f_score[neighbor]
    
    return "no path found"

The structure is nearly identical to Dijkstra's algorithm. The only difference is how we prioritize nodes: Dijkstra uses $g(n)$ alone, while A* uses $f(n) = g(n) + h(n)$.

When to use A* vs Dijkstra:

• Use A* when you have a single target and a good heuristic. It will find the optimal path faster.
• Use Dijkstra when you need shortest paths to all nodes, or when no good heuristic exists.

Visualizing in 3D

Pathfinding isn't limited to flat grids. On terrain with hills and valleys, the cost of traversal varies with elevation. Watch A* navigate a 3D landscape, finding the optimal path that balances distance and elevation change.

Drag to rotate the view. Notice how the search naturally avoids steep climbs when a gentler path exists nearby.

Key Takeaways

• A* combines actual distance ($g$) with heuristic estimate ($h$) into a total score $f = g + h$
• The priority queue orders nodes by $f(n)$—lowest total estimated cost first
• A* explores fewer nodes than Dijkstra while still finding the optimal path
• An admissible heuristic (one that never overestimates) guarantees optimality
• A* is the most widely used pathfinding algorithm in games, robotics, and navigation systems
• The algorithm stretches its frontier toward the goal, creating an elliptical rather than circular search pattern