Edit the graph and the cost on each link, pick a start and a goal, then press Play. A* ranks every node by f = g + h: g is the cost of the path so far and h is the straight-line distance to the goal. It expands the node with the smallest f, so it balances "cheap so far" against "looks close to the goal". Drag nodes around to change h.
Not found yetIn the queueExpanding nowExpandedPath foundUnder a node: g = cost so far, h = distance to the goal, f = g + h. The number on a link is its cost.
Step 0 of 0
Order of expansion
Nodes appear here in the order they leave the queue. The small number beside each one is its f value when it was expanded.
Adjacency table
Every node with its links, costs, and g, h and f values. Click a row to select that node.
Node
Connected to (cost)
g
h
f
Status
The algorithm
The highlighted lines are the ones running in the current step.
A* (A star) search finds the cheapest path from a start node to a goal. It ranks every node in its priority queue by f(n) = g(n) + h(n), where g(n) is the exact cost of the best path found so far and h(n) is a heuristic estimate of the cost still to go. It combines the strengths of Uniform Cost Search, which is careful about cost, and Greedy Best-First Search, which is drawn toward the goal. When h never overestimates, A* is guaranteed to return a cheapest path, usually after expanding far fewer nodes than Uniform Cost Search.
f = g + h
Priority — the cost so far plus the estimate of the cost to go
Optimal*
Finds the cheapest path when h is admissible, meaning it never overestimates
O((V + E) log V)
Worst-case time with a heap. A good heuristic usually does much better
O(V)
Space complexity — it keeps every discovered node in memory
How it works
Put the start node in the priority queue with g = 0 and f = 0 + h.
Take out the entry with the smallest f. If two tie, the one with the smaller h goes first.
Mark it as expanded. If it is the goal, stop and follow the parent links back to the start.
Otherwise look at each neighbour that is not expanded. Its new g is the current g plus the link cost.
If the neighbour is new, add it with f = g + h. If the new g beats the one it has, update its entry and its parent. Otherwise ignore it.
Repeat from step 2 until the goal is taken out or the queue is empty.
Key properties
The heuristic: here h is the straight-line distance to the goal on the canvas divided by 40 and rounded down. Dragging a node changes h.
Admissible h: h never overestimates the true remaining cost. Then the first time the goal leaves the queue, its path is the cheapest. The page checks this for you and warns when h is too high.
Link costs matter: straight-line h stays admissible only if each link costs at least its drawn length divided by 40. A cheap "shortcut" link breaks this. Try the "Bad heuristic" example.
Special cases: with h = 0 everywhere, A* is Uniform Cost Search. If it ignores g, it is Greedy Best-First Search.
Better h, fewer nodes: an estimate closer to the true cost lets A* skip more of the graph, as long as it never goes over.
Worked example
Same graph as the default example in the Visualizer. Go from A to G. Each node is ranked by f = g + h: g is the cost so far and h is the straight-line distance to G (units of 40 px, rounded down). Ties go to the smaller h.
Default map with h values.
Queue A: g=0, h=14, f=14.
Pop A. Add B (g=6, f=16), C (g=5, f=15), D (g=6, f=17).
Pop C (f=15). Add F (g=11, f=16). Routes to B and D via C cost 9, not better than 6, so keep the old ones.
B and F tie at f=16; F has the smaller h (5 vs 10), so pop F. Add G (g=17, f=17) and H (g=17, f=22).
Pop B (f=16). Add E (g=12, f=17).
G, E and D all have f=17; G has the smallest h (0). Pop G. It is the goal, so stop.
Cheapest path: A → C → F → G, total cost 17. A* never expanded D, E, or H, and the heuristic never overestimates here, so the path is optimal.
Where A* is used
GPS navigation
Finding the fastest route between two places using straight-line distance as the guide.
Video game AI
Moving characters around walls and terrain quickly and cheaply.
Robotics
Planning collision-free motion for robots and vehicles.
Puzzle solving
Sliding-tile puzzles and similar problems, using "tiles out of place" as h.
Network routing
Choosing low-cost paths through a network when a good estimate is available.
Logistics
Planning delivery and warehouse routes that minimise distance or time.
Switch back to the Visualizer tab to build a graph and watch g, h and f change as the search runs.