Suppose you need the cheapest route across a city, but you only care about one destination. Dijkstra’s algorithm may explore streets in every direction. A* adds an estimate of the distance still to go, helping the search lean toward the goal without giving up the shortest-path guarantee when the heuristic meets the required conditions. section 12.0 section 12.1
For each node n, A* keeps three values:
- g(n): the actual cost from the start to n. section 12.4
- h(n): a cheap estimate of the remaining cost to the goal. section 12.4
- f(n) = g(n) + h(n): the estimated total cost. A* expands the queued node with the smallest f value. section 12.4
The estimate must be admissible: it must never exceed the true remaining cost. Straight-line distance is an example for road routes; Manhattan distance works for movement restricted to four grid directions. A stronger property, consistency, means an expanded node need not be reopened. section 12.1 section 12.4
Do not stop when you first see the goal
On a six-intersection map, A* first finds a route to the goal costing 11. Another node still has a lower f value, so the search continues. Expanding it reveals a route costing 10. A* updates the goal’s cost and parent pointer, then finishes when the goal comes off the priority queue. Following parent pointers recovers the cheaper path. section 12.1
Listing 12.1 Pseudocode of A* Algorithm
function A_STAR(start, goal):
open_set = priority queue ordered by f, containing {start}
g[start] = 0
f[start] = h(start)
came_from = empty map
while open_set is not empty:
current = node in open_set with smallest f
if current == goal:
return reconstruct_path(came_from, current)
remove current from open_set
for each neighbor of current:
tentative_g = g[current] + cost(current, neighbor)
if tentative_g < g[neighbor] (or neighbor has no g yet):
came_from[neighbor] = current
g[neighbor] = tentative_g
f[neighbor] = tentative_g + h(neighbor)
add neighbor to open_set if not already present
return "no path exists"
The pseudocode shows the working loop: take the lowest-f node, test for the goal, improve neighbors’ g values when possible, and record their parents for path reconstruction. section 12.1
A weak heuristic can leave A* exploring as much as Dijkstra. With a binary priority queue, worst-case time is O((V + E) log V). Memory is often the tougher limit because discovered nodes retain scores and parent pointers. Iterative Deepening A* (IDA*) trades repeated search work for a smaller memory footprint. section 12.3





