A* Search

Dijkstra explores outward in every direction like ripples in a pond — it has no idea where the goal is. A* adds intelligence. It keeps everything Dijkstra gives you — correctness, optimality, priority queue mechanics — and injects a heuristic that pulls the search toward the destination. The result: same optimal path, dramatically fewer nodes explored.

If Dijkstra is a blindfolded explorer checking every corridor, A* is the same explorer with a compass pointing toward the exit.

The Cost Function: f(n) = g(n) + h(n)

A* assigns every node a total estimated cost f(n) composed of two parts:

g(n): the actual, known cost from the start node to node n. This comes from accumulating edge weights along the path so far — identical to what Dijkstra tracks.
h(n): the estimated cost from node n to the goal. This is the heuristic — your educated guess about the remaining distance.
f(n) = g(n) + h(n): the estimated total cost of the cheapest path from start to goal that goes through node n.

Dijkstra uses g(n) alone to order its priority queue. A* uses f(n). That single change turns an undirected search into a goal-directed one.

Think of it this way: g(n) looks backward — “how much have I spent?” h(n) looks forward — “how much do I expect to spend?” f(n) combines both to answer — “what’s the total expected trip cost through this node?”

The Algorithm

The structure mirrors Dijkstra almost exactly. The only difference is the priority queue ordering.

record AStarNode(int row, int col, int g, int f) implements Comparable<AStarNode> {
    @Override
    public int compareTo(AStarNode other) {
        return Integer.compare(this.f, other.f);  // Order by f(n), not g(n)
    }
}

Steps:

Initialize the start node with g = 0, f = h(start).
Add the start node to a priority queue ordered by f(n).
Extract the node with the smallest f(n).
If this node is the goal → done. Reconstruct the path.
For each neighbor, compute tentative g = current.g + edge cost.
If this g is better than any previously recorded g for that neighbor, update it and add to the PQ with f = g + h(neighbor).
Repeat until the goal is extracted or the PQ is empty (no path exists).

The priority queue always surfaces the node that appears most promising — the one with the lowest estimated total cost. This is why A* reaches the goal faster than Dijkstra: it doesn’t waste time exploring nodes in the wrong direction.

Heuristics: The Make-or-Break Decision

The heuristic h(n) is what separates a brilliant A* implementation from a broken one. Two properties matter:

Admissible Heuristics

A heuristic is admissible if it never overestimates the true cost to the goal:

$$h(n) \leq \text{actual cost from } n \text{ to goal}$$

Admissibility guarantees optimality. If h never overestimates, A* never prematurely commits to a suboptimal path because the estimated total cost f(n) always remains a lower bound on the true path cost through n.

Consistent (Monotone) Heuristics

A heuristic is consistent if for every node n and every neighbor n’:

$$h(n) \leq \text{cost}(n, n’) + h(n’)$$

This is the triangle inequality applied to the heuristic. Consistency implies admissibility (but not the reverse). A consistent heuristic guarantees that once you extract a node from the priority queue, you’ve found the shortest path to it — no need to revisit. This allows using a closed set to skip already-processed nodes, delivering a significant performance boost.

Every heuristic used in practice is consistent. Constructing an admissible-but-inconsistent heuristic requires deliberate effort.

Common Grid Heuristics

Heuristic	Formula	Best For
Manhattan	\|x₁-x₂\| + \|y₁-y₂\|	4-directional grid movement
Euclidean	√((x₁-x₂)² + (y₁-y₂)²)	Any-angle movement
Chebyshev	max(\|x₁-x₂\|, \|y₁-y₂\|)	8-directional grid movement
Zero	0	Degenerates to Dijkstra
Perfect	actual shortest distance	Oracle — A* goes straight to goal

Manhattan distance works for grids where you move up/down/left/right. It counts the minimum number of steps ignoring obstacles — always admissible because obstacles can only increase the true cost, never decrease it.

Euclidean distance works for continuous movement. It’s the straight-line distance — physically impossible to beat, so always admissible.

Setting h(n) = 0 tells A* “I have no idea how far the goal is,” causing it to rely entirely on g(n). It becomes Dijkstra. Setting h(n) equal to the true shortest distance gives A* perfect foresight — it expands only nodes on the optimal path. Every practical heuristic falls somewhere between these two extremes.

Grid Implementation

Here is a complete A* implementation for a 2D grid with obstacles:

int[][] aStarGrid(int[][] grid, int[] start, int[] goal) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[start[0]][start[1]] = 0;

    int[][] parent = new int[rows][cols];
    for (int[] row : parent) Arrays.fill(row, -1);

    PriorityQueue<AStarNode> pq = new PriorityQueue<>();
    int h = manhattan(start[0], start[1], goal[0], goal[1]);
    pq.offer(new AStarNode(start[0], start[1], 0, h));

    boolean[][] visited = new boolean[rows][cols];
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    while (!pq.isEmpty()) {
        AStarNode curr = pq.poll();
        int r = curr.row(), c = curr.col();

        if (r == goal[0] && c == goal[1]) {
            return reconstructPath(parent, start, goal);
        }

        if (visited[r][c]) continue;
        visited[r][c] = true;

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] == 1 || visited[nr][nc]) continue;  // 1 = obstacle

            int newG = curr.g() + 1;
            if (newG < dist[nr][nc]) {
                dist[nr][nc] = newG;
                int newF = newG + manhattan(nr, nc, goal[0], goal[1]);
                pq.offer(new AStarNode(nr, nc, newG, newF));
                parent[nr][nc] = r * cols + c;  // Encode parent position
            }
        }
    }
    return new int[0][];  // No path found
}

int manhattan(int r1, int c1, int r2, int c2) {
    return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}

The visited array acts as the closed set. Because Manhattan distance is consistent, the first time we extract a node, we’ve found the shortest path to it. The inner loop checks all four neighbors, computes the tentative g-cost, and only adds the neighbor if the new path is cheaper than any previously discovered one.

Visual Walkthrough

Consider this 5×5 grid (S = start, G = goal, █ = wall, · = open):

S · · · ·
· · █ · ·
· · █ · ·
· · · · ·
· · · · G

Dijkstra explores outward uniformly from S. It checks nodes in the top-left corner, the left edge, and the bottom-left — all irrelevant to reaching G in the bottom-right. Total nodes explored: ~20.

A* with Manhattan distance immediately biases toward the bottom-right. It still explores some nodes off the optimal path (the heuristic isn’t perfect), but the funneling effect skips large portions of the grid. Total nodes explored: ~12.

The wall forces both algorithms to route around the obstacle. A* discovers the detour faster because nodes below the wall have lower f-values than nodes above it and to the left. The heuristic keeps pulling the search downward and to the right.

When A* Becomes BFS or Dijkstra

A* is a generalization. By adjusting the graph and heuristic, it collapses into familiar algorithms:

Graph Type	Heuristic	A* Becomes
Unweighted	h = 0	BFS
Weighted, non-negative	h = 0	Dijkstra
Any	Admissible h > 0	A* (optimal, fewer nodes)
Any	Inadmissible h	Weighted A* (fast, not optimal)

Think of BFS and Dijkstra as A* with no compass. They work, but they wander. An admissible heuristic adds directional awareness without sacrificing correctness.

Why A* Finds the Optimal Path

Here’s the core argument. Suppose A* extracts the goal node G with cost f(G). Is this the optimal path?

Assume for contradiction that a cheaper path P* exists with cost c* < f(G). At the point when G was extracted, P* had some frontier node n still in the priority queue. Because h is admissible:

$$f(n) = g(n) + h(n) \leq g(n) + \text{actual remaining cost} = c^*$$

So f(n) ≤ c* < f(G). But A* extracted G before n, meaning f(G) ≤ f(n). This contradicts f(n) < f(G). Therefore, no cheaper path exists. The first path to the goal that A* extracts from the priority queue is optimal.

This proof depends entirely on admissibility. If h overestimates, the inequality breaks and A* can return suboptimal paths.

Practical Considerations

Memory

A* stores every explored node in the closed set and every frontier node in the open set (priority queue). For large state spaces — think a 1000×1000 grid or a complex game state — this memory consumption becomes the bottleneck, not CPU time.

IDA* (Iterative Deepening A*)

IDA* trades time for memory. It runs depth-first search with a threshold on f(n):

Set threshold = f(start) = h(start).
Run DFS, pruning any node where f(n) > threshold.
If goal not found, set threshold = minimum f(n) among pruned nodes.
Repeat.

Each iteration explores deeper, and DFS uses O(depth) memory instead of O(explored nodes). IDA* is the standard approach for the 15-puzzle, Rubik’s cube solvers, and other problems where the state space is immense but the solution depth is bounded.

Applications

GPS navigation: road networks with distances as edge weights, straight-line distance as heuristic.
Video game pathfinding: grid or navmesh with obstacles, Manhattan or Euclidean heuristic.
Robotics: configuration space search for collision-free paths.
Puzzle solving: 15-puzzle (Manhattan distance of tiles), Rubik’s cube (pattern database heuristic).

A* in Coding Interviews

A* rarely appears as the expected solution in standard coding interviews. Most shortest-path interview problems use BFS (unweighted) or Dijkstra (weighted). However, A* shows up in:

Game development interviews where pathfinding is a core requirement.
Robotics and autonomous vehicle teams that need real-time path planning.
Problems where the interviewer asks “can you optimize Dijkstra if you know the goal location?”

Even when A* isn’t the answer, mentioning the heuristic concept demonstrates algorithmic maturity. Saying “we could reduce explored nodes with an admissible heuristic” signals that you think beyond textbook algorithms.

Comparison: BFS vs Dijkstra vs A*

Property	BFS	Dijkstra	A*
Graph type	Unweighted	Non-negative weights	Non-negative weights
Data structure	Queue	Min-heap by g(n)	Min-heap by f(n)
Handles weights	No	Yes	Yes
Uses heuristic	No	No	Yes
Optimal	Yes (unweighted)	Yes	Yes (admissible h)
Nodes explored	Many	Many	Fewer (guided)
Time complexity	O(V + E)	O((V + E) log V)	O((V + E) log V) worst case
Space complexity	O(V)	O(V)	O(V)
Best for	Unweighted BFS	General shortest path	Goal-directed search

All three algorithms belong to the same family. BFS expands nodes by hop count. Dijkstra expands by accumulated cost. A* expands by accumulated cost plus estimated remaining cost. Each refinement adds information, and information reduces wasted exploration.

Interviewer Tips

“Explain A in one sentence.”* A* is Dijkstra with a heuristic that estimates remaining distance to the goal, enabling the search to prioritize promising directions.

“What happens if your heuristic overestimates?” A* becomes a greedy search — it finds paths faster but they aren’t guaranteed optimal. This is called weighted A* or inadmissible A*, and game developers use it when speed matters more than optimality.

“When would you use A over Dijkstra?”* Whenever you have a clear goal location and can define a meaningful heuristic. A* and Dijkstra produce the same optimal path, but A* gets there by exploring fewer nodes. For problems without a specific goal (like “find shortest paths to all nodes”), Dijkstra is the right choice because A* needs a target to aim at.

“What’s the relationship between the heuristic quality and performance?” The closer h(n) is to the true remaining cost, the fewer nodes A* explores. A perfect heuristic makes A* expand only nodes on the optimal path. A zero heuristic makes it Dijkstra. A poor-but-admissible heuristic still yields optimal paths, but with more exploration. The heuristic is a dial between “correct but slow” and “correct and fast.”