A* Search
Uses Dijkstra plus a heuristic to prioritize nodes closer to the goal, finding an optimal path with an admissible heuristic and non-negative weights.
Optimal:YesWeighted:Yes
Complexity
Best
O((V+E) log V)
Average
O((V+E) log V)
Worst
O((V+E) log V)
Space
O(V)
When to use: Best for weighted grids when you want the optimal path faster than Dijkstra (with a good heuristic).Optimal with an admissible heuristicRequires a heuristic (bad heuristics reduce benefits)
Pseudocode
g[start] ← 0f[start] ← h(start)open ← [start]parent[start] ← nullwhile open not empty:v ← node in open with smallest f[v]for each neighbor u of v:if g[v] + w(v,u) < g[u]:parent[u] ← v; update g[u] and f[u]if goal selected: reconstruct path
Waiting to start…
2
7
2
3
6
4
6
8
8
3
8
8
5
7
9
4