A* (A-Star) Search Algorithm
A* Search finds the optimal shortest path to a target by guiding Dijkstra's algorithm with an admissible heuristic f(n) = g(n) + h(n), dramatically reducing explored nodes.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
A* (A-Star) Search Algorithm
A* Search is an informed shortest-path algorithm that extends Dijkstra's Algorithm by adding a heuristic $h(n)$ estimating the remaining cost from node $n$ to the goal. It prioritizes nodes by:
$f(n) = g(n) + h(n)$
where $g(n)$ is the exact cost from the start to $n$, and $h(n)$ is the estimated cost from $n$ to the goal. When $h(n)$ is admissible (never overestimates the true remaining distance), A* is guaranteed to find the optimal shortest path while exploring far fewer nodes than Dijkstra!
At a Glance
| Property | Value |
| :--- | :--- |
| Time Complexity | $O((V + E) \log V)$ worst case (often much faster with a tight heuristic) |
| Auxiliary Space | $O(V)$ |
| Optimal Shortest Path? | Yes, when $h(n)$ is admissible ($0 \le h(n) \le h^*(n)$) |
| Special Cases | $h(n) = 0 \implies$ Dijkstra; $g(n) = 0 \implies$ Greedy Best-First Search |
| Best Used When | Point-to-point pathfinding on grids, maps, robotics, and puzzle state spaces (8-puzzle, 15-puzzle) |
---
How It Works
1. Initialize g[start] = 0 (all others INF) and push (h(start), 0, start) into a min-heap ordered by f = g + h.
2. While the heap is not empty:
- Pop
(f, gCost, u). IfgCost > g[u], skip stale entry. - If
u == goal, returngCost(optimal!). - For each neighbor
(v, w)ofu: - If
gCost + w < g[v]: setg[v] = gCost + wand push(g[v] + h(v), g[v], v).
procedure aStar(start, goal, h):
g[start] = 0
openSet.push((h(start), 0, start))
while openSet is not empty:
(f, gCost, u) = openSet.popMin()
if gCost > g[u]: continue
if u == goal: return gCost
for (v, w) in adj[u]:
if gCost + w < g[v]:
g[v] = gCost + w
openSet.push((g[v] + h(v), g[v], v))
return NOT_FOUND
Step-by-Step Trace (4-Directional Grid with Manhattan Heuristic)
From (0, 0) to (2, 2) with wall at (1, 1), $h(r, c) = |r - 2| + |c - 2|$:
- Pop
(0, 0):g=0, h=4, f=4→ pushes(0,1)(g=1, h=3, f=4) and(1,0)(g=1, h=3, f=4). - Pop
(0, 1): pushes(0,2)(g=2, h=2, f=4). - Pop
(0, 2): pushes(1,2)(g=3, h=1, f=4). - Pop
(1, 2): pushes(2,2)(g=4, h=0, f=4). - Pop
(2, 2): goal reached with distance4! Nodes moving away from the goal (f = 6) are never even popped.
---
Complexity & Key Insights
- Choosing the Right Heuristic:
- 4-directional grid: Manhattan distance $|r_1 - r_2| + |c_1 - c_2|$.
- 8-directional grid (unit diagonals): Chebyshev distance $\max(|r_1 - r_2|, |c_1 - c_2|)$.
- 8-directional grid ($\sqrt{2}$ diagonals): Octile distance.
- Euclidean plane / GPS maps: Straight-line Euclidean distance $\sqrt{\Delta x^2 + \Delta y^2}$.
- Admissible vs. Consistent: An admissible heuristic never overestimates; a consistent (monotonic) heuristic satisfies $h(u) \le w(u, v) + h(v)$ for every edge, ensuring every node is popped and finalized at most once (just like Dijkstra).
---
Practice Problems
Easy
1. 4-Directional Grid Pathfinding with A* (Manhattan Heuristic)
Find the shortest path from (0, 0) to (R - 1, C - 1) in a binary grid (0 = open, 1 = wall) using A*.
Approach: Use Manhattan distance as the admissible heuristic $h(r, c) = (R - 1 - r) + (C - 1 - c)$. Time: $O(RC \log(RC))$ worst case. Space: $O(RC)$.
<details>
<summary>Show C++ Solution</summary>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
int aStarGrid4(const std::vector<std::vector<int>>& grid) {
int R = static_cast<int>(grid.size()), C = static_cast<int>(grid[0].size());
if (grid[0][0] == 1 || grid[R - 1][C - 1] == 1) return -1;
auto h = [&](int r, int c) { return (R - 1 - r) + (C - 1 - c); };
std::vector<std::vector<int>> g(R, std::vector<int>(C, INT_MAX));
using State = std::tuple<int, int, int, int>; // (f, g, r, c)
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
g[0][0] = 0;
pq.push({h(0, 0), 0, 0, 0});
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (!pq.empty()) {
auto [f, dist, r, c] = pq.top();
pq.pop();
if (dist > g[r][c]) continue;
if (r == R - 1 && c == C - 1) return dist;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 0 && dist + 1 < g[nr][nc]) {
g[nr][nc] = dist + 1;
pq.push({g[nr][nc] + h(nr, nc), g[nr][nc], nr, nc});
}
}
}
return -1;
}
int main() {
std::cout << aStarGrid4({{0, 0, 0}, {1, 1, 0}, {0, 0, 0}}) << "\n";
return 0;
}
</details>
2. 8-Directional Grid Pathfinding (Chebyshev Heuristic, LeetCode 1091)
Find the shortest 8-directional path (including diagonals of cost 1) from (0, 0) to (n - 1, n - 1).
Approach: With unit-cost diagonal moves, Manhattan distance would overestimate (not admissible!). Use Chebyshev distance $h(r, c) = \max(|R - 1 - r|, |C - 1 - c|)$ instead. Time: $O(n^2 \log n)$. Space: $O(n^2)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
int aStarGrid8(const std::vector<std::vector<int>>& grid) {
int n = static_cast<int>(grid.size());
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
auto h = [&](int r, int c) { return std::max(n - 1 - r, n - 1 - c); };
std::vector<std::vector<int>> g(n, std::vector<int>(n, INT_MAX));
using State = std::tuple<int, int, int, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
g[0][0] = 1; // count cells including start
pq.push({1 + h(0, 0), 1, 0, 0});
while (!pq.empty()) {
auto [f, dist, r, c] = pq.top();
pq.pop();
if (dist > g[r][c]) continue;
if (r == n - 1 && c == n - 1) return dist;
for (int dr = -1; dr <= 1; ++dr) {
for (int dc = -1; dc <= 1; ++dc) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && dist + 1 < g[nr][nc]) {
g[nr][nc] = dist + 1;
pq.push({g[nr][nc] + h(nr, nc), g[nr][nc], nr, nc});
}
}
}
}
return -1;
}
int main() {
std::cout << aStarGrid8({{0, 0, 0}, {1, 1, 0}, {1, 1, 0}}) << "\n"; // 4
return 0;
}
</details>
---
Intermediate
3. A* on a 2D Euclidean Road Network with Path Reconstruction
Given cities with (x, y) coordinates and road lengths ($\ge$ Euclidean distance), find and reconstruct the shortest route from src to goal.
Approach: Straight-line Euclidean distance is admissible because no road can be shorter than a straight line. Track parent[v] = u to reconstruct the path. Time: $O((V + E)\log V)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct City { double x, y; };
std::vector<int> aStarRoadPath(const std::vector<City>& cities,
const std::vector<std::vector<std::pair<int, double>>>& adj,
int src, int goal) {
int n = static_cast<int>(cities.size());
auto h = [&](int u) {
double dx = cities[u].x - cities[goal].x;
double dy = cities[u].y - cities[goal].y;
return std::hypot(dx, dy);
};
const double INF = std::numeric_limits<double>::infinity();
std::vector<double> g(n, INF);
std::vector<int> parent(n, -1);
using State = std::pair<double, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
g[src] = 0.0;
pq.push({h(src), src});
while (!pq.empty()) {
auto [f, u] = pq.top();
pq.pop();
if (u == goal) break;
if (f - h(u) > g[u] + 1e-9) continue;
for (const auto& [v, w] : adj[u]) {
if (g[u] + w < g[v]) {
g[v] = g[u] + w;
parent[v] = u;
pq.push({g[v] + h(v), v});
}
}
}
if (g[goal] == INF) return {};
std::vector<int> path;
for (int cur = goal; cur != -1; cur = parent[cur]) path.push_back(cur);
std::reverse(path.begin(), path.end());
return path;
}
int main() {
std::vector<City> cities = {{0, 0}, {2, 1}, {1, 3}, {4, 3}};
std::vector<std::vector<std::pair<int, double>>> adj(4);
adj[0].push_back({1, 2.3}); adj[1].push_back({3, 2.9});
adj[0].push_back({2, 3.2}); adj[2].push_back({3, 3.1});
for (int c : aStarRoadPath(cities, adj, 0, 3)) std::cout << c << " ";
std::cout << "\n";
return 0;
}
</details>
4. Weighted Terrain Pathfinding (Different Cell Costs)
Each cell in a grid has a traversal cost cost[r][c] >= 1. Find the minimum-cost 4-directional path from (0, 0) to (R - 1, C - 1) using A*.
Approach: Since every step costs at least minCost = 1, h(r, c) = minCost ((R - 1 - r) + (C - 1 - c)) is admissible and guides A toward the bottom-right corner. Time: $O(RC \log(RC))$. Space: $O(RC)$.
<details>
<summary>Show C++ Solution</summary>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
int minWeightedGridCost(const std::vector<std::vector<int>>& cost) {
int R = static_cast<int>(cost.size()), C = static_cast<int>(cost[0].size());
auto h = [&](int r, int c) { return (R - 1 - r) + (C - 1 - c); };
std::vector<std::vector<int>> g(R, std::vector<int>(C, INT_MAX));
using State = std::tuple<int, int, int, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
g[0][0] = cost[0][0];
pq.push({g[0][0] + h(0, 0), g[0][0], 0, 0});
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (!pq.empty()) {
auto [f, dist, r, c] = pq.top();
pq.pop();
if (dist > g[r][c]) continue;
if (r == R - 1 && c == C - 1) return dist;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist + cost[nr][nc] < g[nr][nc]) {
g[nr][nc] = dist + cost[nr][nc];
pq.push({g[nr][nc] + h(nr, nc), g[nr][nc], nr, nc});
}
}
}
return -1;
}
int main() {
std::cout << minWeightedGridCost({{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}) << "\n"; // 7
return 0;
}
</details>
---
Hard
5. Sliding Puzzle Solver (8-Puzzle with A* + Manhattan Heuristic)
Given a $3 \times 3$ sliding tile board (0 = blank), find the minimum number of moves to reach "123456780".
Approach: Encode the board as a 9-char string. Use the sum of Manhattan distances of tiles 1..8 from their target positions as the admissible heuristic $h(\text{state})$. A* solves 8-puzzle instances in milliseconds instead of exploring hundreds of thousands of BFS states!
<details>
<summary>Show C++ Solution</summary>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
int manhattan8Puzzle(const std::string& s) {
int sum = 0;
for (int i = 0; i < 9; ++i) {
if (s[i] == '0') continue;
int val = s[i] - '1';
sum += std::abs(i / 3 - val / 3) + std::abs(i % 3 - val % 3);
}
return sum;
}
int solve8Puzzle(const std::string& start) {
const std::string goal = "123456780";
std::unordered_map<std::string, int> g;
using State = std::tuple<int, int, std::string>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
g[start] = 0;
pq.push({manhattan8Puzzle(start), 0, start});
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (!pq.empty()) {
auto [f, dist, cur] = pq.top();
pq.pop();
if (cur == goal) return dist;
if (dist > g[cur]) continue;
int z = static_cast<int>(cur.find('0'));
int r = z / 3, c = z % 3;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
std::string nxt = cur;
std::swap(nxt[z], nxt[nr * 3 + nc]);
if (!g.count(nxt) || dist + 1 < g[nxt]) {
g[nxt] = dist + 1;
pq.push({dist + 1 + manhattan8Puzzle(nxt), dist + 1, nxt});
}
}
}
}
return -1;
}
int main() {
std::cout << "Min moves: " << solve8Puzzle("123405786") << "\n"; // 2
return 0;
}
</details>
---
Related Algorithms
- Dijkstra's Algorithm — A* with heuristic $h(n) = 0$.
- Breadth-First Search (BFS) — unweighted shortest path without heuristics.