AntInLoop

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). If gCost > g[u], skip stale entry.
  • If u == goal, return gCost (optimal!).
  • For each neighbor (v, w) of u:
  • If gCost + w < g[v]: set g[v] = gCost + w and 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 distance 4! 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