Overview
A* Search keeps a frontier ordered by f(n) = g(n) + h(n), where g is the known cost from the start and h estimates the remaining cost to the goal.
CoreSource checked
A* Search
Finds a low-cost path by combining path cost so far with a heuristic estimate to the goal.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Informed Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 25
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- A Star, A-Star
Core Concepts
path costheuristic estimateopen setf-score orderingdistance relaxationgraph representationobjective functioninformed search
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E)
Average
O(E)
Worst
O(E)
Space
O(V)
When to Use
- Use it when a good admissible or consistent heuristic is available.
- Use it for shortest paths to one goal in maps, grids, or state spaces.
- Use it when focusing search toward the goal is more useful than exploring uniformly.
When Not to Use
- Avoid it when the heuristic is misleading enough to behave like brute-force search.
- Avoid it when edge costs are negative.
- Avoid non-admissible heuristics if optimality is required.
What It Does
- Guides graph search with a heuristic
- Finds low-cost paths to a goal
Use Cases
- Game pathfinding
- Robot navigation
- Route planning with a goal
Inputs
- Graph or grid
- Start and goal
- Heuristic function
Outputs
- Path from start to goal
- No-path result
Key Formulas (1)
A* score
f(node) = g(node) + h(node)
f(node) = g(node) + h(node)Ranks each frontier node by known path cost plus estimated remaining cost.
Pseudocode
- 1.Put the start node in an open set
- 2.Score each node by cost so far plus heuristic estimate
- 3.Expand the open node with the lowest score
- 4.Update neighbors when a cheaper route is found
- 5.Stop when the goal is removed from the open set
Canonical Example
- Input
- grid start = (0,0), goal = (2,0), obstacle at (1,0), Manhattan heuristic
- Output
- path around the obstacle
- Explanation
- A* expands states that balance the known path cost with the estimated remaining distance.
Implementation Notes
- Store g-score, f-score, and predecessor separately.
- Use a priority queue ordered by f-score with deterministic tie-breaking when tests need stable paths.
- Treat stale queue entries carefully if decrease-key is not available.
Common Pitfalls
- Using a heuristic that overestimates when optimal paths are required.
- Failing to update or reopen states when a better g-score is found.
- Confusing greedy best-first search with A* by ignoring path cost so far.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the open set moving toward the goal under heuristic guidance.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Put the start node in an open set
grid-pathfindingNotes
With a consistent heuristic, the first time A* removes the goal from the priority queue, the path is optimal.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of A* Search.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsBlock A*
Pathfinding · Core
Block A* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Compare with thisHas variantsHPA*
Pathfinding · Core
HPA* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Compare with thisHas variantsIDA*
Pathfinding · Core
IDA* uses iterative deepening with an A*-style cost bound.
Compare with thisHas variantsLazy Theta*
Pathfinding · Core
Lazy Theta* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Compare with thisRelationships
View full relationship pageGeneralizesD* Lite
D* Lite extends A*-style planning to changing graphs.
Improves onDijkstra's Algorithm
A* adds a heuristic to guide the shortest-path search.
Alternative toGreedy Best-First Search
A* balances path cost and heuristic cost, while greedy best-first focuses on the heuristic.
UsesPriority Queue
A* commonly expands frontier nodes from a priority queue.
Related Algorithms
Tags
Shortest PathHeuristicGraphOptimization