A* Search — Heuristic Shortest Path for Grids and Maps [LC 1091, Google, Tesla]

Problem Statement#

Given a graph (often a grid) with non-negative edge weights, a source s, a target t, and an admissible heuristic h(v) that estimates the remaining distance from v to t, find the shortest path from s to t. A* expands vertices in order of f(v) = g(v) + h(v), where g(v) is the best known distance from s to v. With an admissible (and ideally consistent) heuristic, A* is optimal and often dramatically faster than Dijkstra.

Constraints:

• 1 <= grid size or vertex count <= 10^5
• Edge weights non-negative
• Heuristic must be admissible: h(v) <= true distance from v to t.

Example (8-direction grid path):

Input:  grid = [[0,0,0],[1,1,0],[1,1,0]], start = (0,0), end = (2,2)
Output: 4   (path 0,0 -> 0,1 -> 0,2 -> 1,2 -> 2,2)
Heuristic: Chebyshev distance to end (admissible for 8-direction movement).

Why This Problem Matters#

A* is the pathfinding workhorse of modern software. Google Maps blends A* with contraction hierarchies. Game engines from Unity to Unreal expose A* as their default navigation algorithm. Robotics motion planners (ROS Navigation Stack, MoveIt) use A* and its variants. Tesla and Waymo use A*-derived planners for low-level path planning before handing off to optimal control.

In FAANG interviews A* is rarely demanded by name, but problems like LeetCode 1091 (Shortest Path in Binary Matrix), LeetCode 773 (Sliding Puzzle), and LeetCode 1293 (Shortest Path in a Grid with Obstacles Elimination) admit elegant A* solutions. Knowing when to upgrade from BFS or Dijkstra to A* — and being able to articulate admissibility and consistency — earns serious bonus points.

A* is also the algorithm that taught a generation of engineers how to think about heuristics. The same idea reappears in IDA*, weighted A*, RRT, and iterative deepening searches across AI planning. Interviews at Google, Tesla, and Amazon Robotics test this knowledge directly.

The Core Insight#

A* generalises both Dijkstra (when h = 0) and Greedy Best-First Search (when g = 0). It pulls the next vertex to expand from a min-heap keyed on:

f(v) = g(v) + h(v)

g(v) is the cost from start to v along the best-known path. h(v) is a heuristic estimate of the remaining cost to the goal. If h never overestimates the true remaining cost, the heuristic is admissible and A* returns an optimal path.

If h is also consistent (also called monotone) — meaning h(u) <= cost(u, v) + h(v) for every edge — then once a vertex is popped from the heap its g value is final, and A* never revisits it. With only admissibility, you may need to allow re-expansion when a cheaper g is found later.

Common admissible heuristics on grids:

• Manhattan distance |dx| + |dy| for 4-direction movement with unit costs.
• Chebyshev distance max(|dx|, |dy|) for 8-direction movement with unit costs.
• Euclidean distance sqrt(dx^2 + dy^2) for arbitrary continuous movement.

The closer h is to the true distance without overestimating it, the faster A* runs. With a tight admissible heuristic, A* often expands orders of magnitude fewer vertices than Dijkstra.

Visual Dry Run#

3x3 grid with no obstacles, 8-direction movement. Start (0,0), end (2,2). Heuristic: Chebyshev distance to end.

A* found the optimal 2-step diagonal path after only 3 pops. Dijkstra would have popped many more cells before discovering the goal because it has no notion of direction toward the target.

Solution (Optimal)#

Python#

import heapq
from math import inf
 
def a_star(grid, start, end):
    """
    grid: 2D matrix of 0 (open) and 1 (blocked).
    Returns shortest 8-direction path length from start to end, or -1.
    """
    rows, cols = len(grid), len(grid[0])
    if grid[start[0]][start[1]] or grid[end[0]][end[1]]:
        return -1
 
    def h(p):
        # Chebyshev distance: admissible for 8-direction unit-cost movement.
        return max(abs(p[0] - end[0]), abs(p[1] - end[1]))
 
    g_score = { start: 0 }
    open_heap = [(h(start), 0, start)]  # (f, g, point)
 
    while open_heap:
        f, g, u = heapq.heappop(open_heap)
        if u == end:
            return g + 1  # +1 to count both endpoints in path length
        if g > g_score.get(u, inf):
            continue  # stale entry, a better path was found earlier
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                if dx == 0 and dy == 0:
                    continue
                nx, ny = u[0] + dx, u[1] + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
                    new_g = g + 1
                    if new_g < g_score.get((nx, ny), inf):
                        g_score[(nx, ny)] = new_g
                        heapq.heappush(open_heap, (new_g + h((nx, ny)), new_g, (nx, ny)))
    return -1

JavaScript#

function aStar(grid, start, end) {
    const rows = grid.length, cols = grid[0].length;
    if (grid[start[0]][start[1]] || grid[end[0]][end[1]]) return -1;
 
    const h = ([r, c]) => Math.max(Math.abs(r - end[0]), Math.abs(c - end[1]));
    const key = ([r, c]) => r * cols + c;
 
    // Min-heap helper
    const heap = [];
    const push = (item) => { heap.push(item); up(heap.length - 1); };
    const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; down(0); } return top; };
    const up = (i) => { while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
    const down = (i) => { const n = heap.length; while (true) { const l = 2*i+1, r = 2*i+2; let s = i; if (l<n && heap[l][0]<heap[s][0]) s=l; if (r<n && heap[r][0]<heap[s][0]) s=r; if (s===i) break; [heap[s], heap[i]] = [heap[i], heap[s]]; i = s; } };
 
    const gScore = new Map();
    gScore.set(key(start), 0);
    push([h(start), 0, start]);
 
    while (heap.length) {
        const [, g, u] = pop();
        if (u[0] === end[0] && u[1] === end[1]) return g + 1;
        if (g > (gScore.get(key(u)) ?? Infinity)) continue;
        for (let dr = -1; dr <= 1; dr++) {
            for (let dc = -1; dc <= 1; dc++) {
                if (dr === 0 && dc === 0) continue;
                const nr = u[0] + dr, nc = u[1] + dc;
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (grid[nr][nc] !== 0) continue;
                const ng = g + 1;
                const k = key([nr, nc]);
                if (ng < (gScore.get(k) ?? Infinity)) {
                    gScore.set(k, ng);
                    push([ng + h([nr, nc]), ng, [nr, nc]]);
                }
            }
        }
    }
    return -1;
}

Complexity: Worst case O((V + E) log V), same as Dijkstra. With a tight admissible heuristic, the practical number of expansions is often a small fraction of Dijkstra's.

Common Mistakes#

1. Inadmissible heuristic. Using a heuristic that overestimates true distance breaks optimality. Manhattan distance on an 8-direction grid is inadmissible because it overestimates — Chebyshev is the correct choice.
2. Inconsistent heuristic without re-expansion. With only admissibility (not consistency), some vertices may need to be re-expanded with a smaller g. Without that allowance, you may return suboptimal paths.
3. Using A on graphs with negative edges.* A* requires non-negative edge weights, just like Dijkstra.
4. Heavy heuristic computation. If h is expensive to evaluate, A* may be slower than Dijkstra. Cache or simplify the heuristic.
5. Forgetting the stale-entry check. Heap entries may become outdated when a cheaper g is later found. Skip them with if g > gScore[u]: continue.
6. Using A when BFS already suffices.* On unweighted graphs the simpler BFS is faster (no heap). A* shines when there is a weight differential or when the graph is huge but the goal is in a clear direction.

Interview Tips#

• Define admissibility and consistency in plain English: "never overestimate" and "the triangle inequality on the heuristic."
• Walk through how A* reduces to Dijkstra when h = 0 and to greedy best-first when g = 0.
• For LeetCode 1091, mention that A* with Chebyshev heuristic is a strict improvement over BFS in expected runtime.
• Mention weighted A* (multiplying h by 1 + epsilon) as a real-world tradeoff: optimality is sacrificed for speed.
• For very large state spaces, mention IDA* (iterative deepening A*) which uses depth-first search with an f threshold to bound memory.

Follow-up Questions#

1. What is bidirectional A?* Run two A* searches simultaneously from start and end and stop when they meet. Often much faster than unidirectional A*.
2. What is weighted A?* Use f(n) = g(n) + w * h(n) with w > 1. Faster but no longer optimal — solution within factor w of optimal.
3. LeetCode 773 (Sliding Puzzle): A* with Manhattan-distance-of-tiles-from-goal heuristic.
4. What is Theta?* A variant for grids that allows any-angle paths instead of restricting to grid edges.
5. How does A compare to Jump Point Search?* JPS prunes redundant grid expansions for uniform-cost grids and is often 10x faster than A* for that specific case.

Key Takeaways#

• A* is best-first search that minimises f(v) = g(v) + h(v) and is the gold standard for goal-directed shortest path search.
• An admissible heuristic (never overestimates true distance) guarantees optimality.
• A consistent heuristic ensures every vertex is finalised on first pop — no re-expansion required.
• A* generalises Dijkstra (h = 0) and greedy best-first (g = 0).
• Manhattan, Chebyshev, and Euclidean distances are the standard admissible heuristics for grid problems.
• FAANG, Tesla, and game-AI interviews use A* indirectly through pathfinding problems like LeetCode 1091, 773, and 1293.