A* Algorithm Visualizer

Pseudocode

A* is Dijkstra with one extra term. Where Dijkstra always expands the node with the smallest confirmed cost g, A* expands the one with the smallest f = g + h, where h estimates the cost still to go. Set h to zero everywhere and the pseudocode below becomes Dijkstra exactly.

A*(graph, start, goal, h):
    for each vertex v: g[v] = infinity
    g[start] = 0
    f[start] = h(start)
    open = priority queue containing (f[start], start)
    closed = empty set

    while open is not empty:
        u = open.extractMin()          // smallest f
        if u == goal: return reconstruct(u)
        add u to closed

        for each edge (u, v, w):
            if v in closed: continue
            tentative = g[u] + w
            if tentative < g[v]:
                previous[v] = u
                g[v] = tentative
                f[v] = tentative + h(v)
                open.insert(f[v], v)

    return no path

The closed-set skip on line 15 is only safe when h is consistent, meaning h(u) <= w(u, v) + h(v) for every edge. With a merely admissible heuristic you must allow nodes to leave the closed set and be reopened, or A* can return a suboptimal path. The visualizer above scales straight-line distance by the cheapest cost-per-unit any edge offers, which makes h consistent by the triangle inequality, so no reopening is needed.

Worked example, step by step

Five nodes, with S at the origin and the goal G five units to its right. The point of the trace is the node A* never touches.

Example graph: S(0,0), A(2,1), B(2,-1), C(1,4), G(5,0). Edges S-A = 3, S-B = 2, S-C = 4, A-B = 2, A-G = 4, B-G = 6, C-G = 7. Scaling straight-line distance by the cheapest cost-per-unit on any edge (0.894) gives h(S) = 4.47, h(A) = 2.83, h(B) = 2.83, h(C) = 5.06, h(G) = 0.

1. 1. Expand S, the only open node, at f = 4.47. Relaxing its three edges sets A to g = 3, f = 5.83; B to g = 2, f = 4.83; and C to g = 4, f = 9.06. C already looks expensive: it is close to S but points away from the goal.
2. 2. Expand B, now the smallest f at 4.83. It reaches the goal at g = 8, f = 8.00. Note that A* does not stop here. Finding the goal is not the same as expanding it, and 8 is not yet known to be best.
3. 3. Expand A at f = 5.83. Its edge to G gives g = 7, beating the 8 found through B, so G improves to f = 7.00.
4. 4. Expand G at f = 7.00, the smallest f in the open set. The goal has been expanded, so its cost is final and the search stops with C still sitting untouched in the open set at f = 9.06.

A* returns S to A to G at a cost of 7, having expanded 4 nodes. Dijkstra on the same graph returns the identical path at the identical cost, but expands 5: it works through C before it is willing to settle the goal. C was never worth visiting, and h is what let A* know that without checking.

Complexity, and where it comes from

Time: O((V + E) log V) worst case with a binary heap · Space: O(V)

The worst case is Dijkstra's, and for the same reason: every vertex can enter the priority queue once and every edge can trigger one decrease-key, giving V extractions and E updates at O(log V) each. The heuristic changes none of that bound. What it changes is the constant: nodes whose f exceeds the goal's final cost are never expanded at all. With h = 0 A* degenerates to Dijkstra exactly; with a perfect h it walks straight down the optimal path expanding only its vertices. Across 4000 randomly generated weighted graphs, the implementation above expanded 4.58 nodes on average against Dijkstra's 5.52, and returned the optimal cost every single time.

When to use A* Search Algorithm, and when not to

A* is worth its extra machinery only when you have a goal and a usable estimate of the distance to it. Without either, one of these is the better tool.

Common pitfalls

• An overestimating heuristic breaks optimality. If h can exceed the true remaining cost, A* may settle the goal through a route that is not cheapest, and it will do so silently. Straight-line distance is admissible only when it is in the same units as your edge weights. Pixel distance against weights of 1 to 10 overestimates wildly.
• Admissible is not the same as consistent. The closed set assumes consistency, h(u) <= w(u, v) + h(v) on every edge. A heuristic that is admissible but inconsistent needs nodes to be reopened when a cheaper route to them appears, otherwise the returned path can be suboptimal.
• Stopping when the goal is first discovered. Reaching the goal during edge relaxation proves nothing. In the trace above, B finds G at cost 8 one step before A finds it at 7. You must wait until the goal is the node being expanded.
• Recomputing h on every comparison. The heuristic is called once per node, not once per priority-queue comparison. Caching h alongside g is the difference between a heuristic that pays for itself and one that costs more than it saves.
• Assuming A* always beats Dijkstra. With a weak heuristic A* expands the same nodes as Dijkstra plus the overhead of computing h. On graphs with no geometry, h = 0 is the honest choice and Dijkstra is the simpler implementation.

Frequently asked questions

What does f = g + h actually mean?

g is what a path to this node has cost so far, and it is a fact. h is a guess at what getting from here to the goal will cost. Their sum f is the estimated cost of the cheapest complete route through this node, and A* always works on the node with the smallest estimate.

What makes a heuristic admissible?

It never overestimates the true remaining cost. Straight-line distance qualifies for travel on a plane, because no route can be shorter than a straight line. Admissibility is what guarantees A* returns an optimal path.

Is A* always faster than Dijkstra?

It never expands more nodes than Dijkstra given the same graph and a consistent heuristic, and usually expands fewer. But it is not asymptotically faster: both are O((V + E) log V). The gain is a constant factor, and it shrinks to nothing as the heuristic weakens towards zero.

Can A* handle negative edge weights?

No. It inherits the assumption that makes Dijkstra work, namely that extending a path never makes it cheaper. Use Bellman-Ford when weights can be negative.

Who invented A*?

Peter Hart, Nils Nilsson and Bertram Raphael, at Stanford Research Institute, in a 1968 paper titled "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". A 1972 note by the same authors corrected the original optimality claim, distinguishing admissibility from consistency.

Why did A* skip node C in the walkthrough?

C sits at f = 9.06 while the goal was settled at f = 7.00. Because the heuristic never overestimates, an f of 9.06 is a promise that no route through C can cost less than 9.06, which is already worse than a finished answer of 7. A* can discard it without looking.