Overview
Weighted A* is a pathfinding method that searches a graph, grid, or configuration space using costs, heuristics, or incremental updates. It is useful when route quality, replanning cost, or search speed matters more than a naive traversal.
CoreSource checked
Weighted A*
Weighted A* finds routes through graphs, grids, or motion-planning spaces.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Pathfinding
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
state spacepath costsearch frontierfrontiercost estimatepath reconstruction
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E)
Average
O(E log V)
Worst
O(E log V)
Space
O(V)
When to Use
- Use Weighted A* when the map, costs, and movement rules match its search assumptions.
- Use it when route quality and search budget must be balanced explicitly.
When Not to Use
- Avoid when the heuristic or cost model does not match the real movement constraints.
- Avoid when dynamic updates make a simpler replanning strategy easier to validate.
What It Does
- Searches a state space for routes
- Uses costs, heuristics, or incremental updates
- Returns a route or reachable region
Use Cases
- Game navigation
- Robotics planning
- Route planning
Inputs
- Graph, grid, or map
- Start and goal
- Costs or heuristic
Outputs
- Path
- Distance estimate
- Search tree
Key Formulas (1)
Weighted A* score
f(n) = g(n) + w · h(n)
f(n) = g(n) + w * h(n)Inflates the heuristic to trade optimality for faster search.
Pseudocode
- 1.Initialize start state, goal state, and search records
- 2.Select the next frontier node using cost, heuristic, or sampling rule
- 3.Expand reachable neighbors or samples
- 4.Update path costs and parent links
- 5.Return the reconstructed path or failure result
Canonical Example
- Input
- grid with start S and goal G
- Output
- route from S to G or no path
- Explanation
- Weighted A* expands candidate states and reconstructs a path when the goal is reached.
Implementation Notes
- Keep cost, heuristic, and parent-link updates in separate steps.
- Test blocked, unreachable, and changing-cost maps.
Common Pitfalls
- Using an inadmissible heuristic while expecting optimal paths gives incorrect guarantees.
- Forgetting to update parent links makes path reconstruction fail.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the frontier expanding through the map and the final path being reconstructed.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Initialize start state, goal state, and search records
pathfindingNotes
Weighted A* operates in O(E log V) time and O(V) space within the Pathfinding family. Key governing relation: f(n) = g(n) + w * h(n). Often compared with A* Search and Dijkstra's Algorithm.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Weighted A*.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toA* Search
Weighted A* is a route-search alternative to A* Search with different heuristic or replanning behavior.
Related Algorithms
Tags
PathfindingGraph