History
Peter Hart, Nils Nilsson, and Bertram Raphael published A* in 1968 while working on the Shakey mobile robot project at Stanford Research Institute. Their goal was to search efficiently without losing the guarantee of an optimal route.
Graph algorithms / interactive lesson
A* Search Algorithm
Find a shortest route to one target with informed search. Compare the exact traveled cost g, the heuristic estimate h, and the combined priority f while A* focuses its exploration.
University
Guided lesson
Snapshot 1/24
A* search space / cyan inspection / orange relaxation / green best-known route
Decision timeline
Start at A and aim for F
About the algorithm
A* finds a low-cost route from one source to one target. It combines the exact distance already traveled, g(n), with a heuristic estimate of the distance still remaining, h(n). The sum f(n) = g(n) + h(n) decides which possibility to explore next.
How it works
Keep discovered nodes in an open set. Repeatedly expand the node with the lowest f score. Relax its neighbors by improving their g scores when a cheaper route appears. With an admissible heuristic, the first selected goal node completes an optimal path.
Where it is used
A* is a standard tool for game navigation, robotics, route planning, puzzle solving, and AI search. A useful heuristic reduces exploration dramatically. If the heuristic is always zero, A* behaves like Dijkstra's algorithm.
Code companion
Connect each visual decision to an implementation pattern.
g[source] = 0
openSet = { source }
while openSet is not empty:
current = node in openSet with minimum g[node] + h[node]
if current == target:
return reconstructPath(predecessor, target)
remove current from openSet
for each neighbor of current:
candidate = g[current] + edge.weight
if candidate < g[neighbor]:
predecessor[neighbor] = current
g[neighbor] = candidate
add neighbor to openSet
return no path