A* Search Algorithm

Introduction

In Phase 3, we explored Dijkstra’s Algorithm, the gold standard for finding the shortest path on a weighted graph.

Dijkstra is mathematically perfect, but it is blind. It explores in expanding circles from the start node, checking every direction equally, completely oblivious to where the target actually is.

Imagine trying to drive from London to Edinburgh. Dijkstra would spend just as much time exploring paths down into France as it would exploring paths north towards Scotland.

We want an algorithm that “pulls” the search towards the destination. We want the A* (A-Star) Search Algorithm.

The Concept: $f(n) = g(n) + h(n)$

A* is simply Dijkstra’s Algorithm with a compass.

In Dijkstra, the Priority Queue ranks nodes purely based on the distance from the start, which we call $g(n)$.

• $g(n)$: The exact cost to travel from the Start to node n.

A* introduces a second metric:

• $h(n)$: The heuristic. An estimate of the remaining distance from node n to the Target.

A* ranks nodes in the Priority Queue based on their total estimated cost, called $f(n)$: -$f(n) = g(n) + h(n)$

Every time A* pops a node from the Priority Queue, it is picking the node that has the lowest total expected path length.

What is a Heuristic?

The heuristic $h(n)$ is the magic that gives A* its speed. It is a mathematical guess.

The golden rule of A* is that the heuristic must be admissible. This means it must never overestimate the true remaining cost. If it overestimates, A* might find a sub-optimal path.

Common Heuristics on a 2D Grid

1. Manhattan Distance: Use this when you can only move in 4 directions (Up, Down, Left, Right). h = abs(current.x - target.x) + abs(current.y - target.y)

2. Euclidean Distance: Use this when you can move at any angle (a straight line). h = sqrt((current.x - target.x)^2 + (current.y - target.y)^2)

Step-by-Step Walkthrough

Let’s imagine a 2D grid. We are at S (Start) and want to reach T (Target). We can move in 4 directions (cost = 1 per step). We use Manhattan Distance as our heuristic.

[.] [.] [.] [T]
[.] [W] [W] [.] 
[S] [.] [.] [.]

(W represents an impassable wall).

Step 1: Start at S (0,0). Target is at (3,2).

• $g(S) = 0$ (steps taken)
• $h(S) = (3-0) + (2-0) = 5$ (Manhattan estimate)
• $f(S) = 0 + 5 = 5$
• Heap: [S(f=5)]

Step 2: Pop S. Check neighbours: Right (1,0) and Up (0,1).

• Node (1,0) [Right]:
  • $g = 0 + 1 = 1$
  • $h = (3-1) + (2-0) = 4$
  • $f = 1 + 4 = 5$
• Node (0,1) [Up]:
  • $g = 0 + 1 = 1$
  • $h = (3-0) + (2-1) = 4$
  • $f = 1 + 4 = 5$
• Heap: [(1,0)(f=5), (0,1)(f=5)]

A* sees two equally good options. Let’s say it checks (1,0) [Right].

Step 3: Pop (1,0). Neighbour is (2,0).

• Node (2,0):
  • $g = 1 + 1 = 2$
  • $h = 3$ (Manhattan to target)
  • $f = 2 + 3 = 5$
• Heap: [(2,0)(f=5), (0,1)(f=5)]

Notice what happens: A* keeps exploring to the right because moving towards the target keeps the $f(n)$ score perfectly stable at 5 ($g$ goes up by 1, $h$ goes down by 1). It completely ignores the nodes going backward or upwards initially because their $f$-scores would increase! It makes a beeline for the target.

When it hits the walls W, the nodes on the other side are unreachable, so checking around the walls increases the $g$ cost significantly while $h$ remains high, causing $f$ to spike. At this point, A* pauses that path and goes back to pop (0,1) from the heap to try the top route instead!

Java Implementation

This code is almost identical to Dijkstra, with two small changes: we add the heuristic calculate method, and we rank the Priority Queue by $f(n)$, not $g(n)$.

import java.util.*;

class Node implements Comparable<Node> {
    int x, y;
    int gCost; // Cost exactly known from start
    int hCost; // Estimated heuristic cost to target
    int fCost; // g + h

    public Node(int x, int y, int gCost, int hCost) {
        this.x = x;
        this.y = y;
        this.gCost = gCost;
        this.hCost = hCost;
        this.fCost = gCost + hCost;
    }

    @Override
    public int compareTo(Node other) {
        // Tie-breaker: if f is equal, prefer the one closer to the target (lower h)
        if (this.fCost == other.fCost) {
            return Integer.compare(this.hCost, other.hCost);
        }
        return Integer.compare(this.fCost, other.fCost);
    }
}

The search loop:

// ... Inside the A* pathfinding method ...

PriorityQueue<Node> openSet = new PriorityQueue<>();
Map<String, Integer> gCosts = new HashMap<>(); // Ledger of absolute best g-costs

// Calculate initial H and add Start node
int startH = calculateManhattan(startX, startY, targetX, targetY);
openSet.offer(new Node(startX, startY, 0, startH));
gCosts.put(startX + "," + startY, 0);

while (!openSet.isEmpty()) {
    Node current = openSet.poll();

    // Did we reach the target?
    if (current.x == targetX && current.y == targetY) {
        return current.gCost; // Shortest path found!
    }

    // Check 4-directional neighbours
    for (int[] dir : new int[][] { {0,1}, {1,0}, {0,-1}, {-1,0} }) {
        int nx = current.x + dir[0];
        int ny = current.y + dir[1];
        
        // Skip walls and out of bounds here...
        
        int tentativeG = current.gCost + 1; // Assuming cost is 1 per step

        // If this is a cheaper path to this neighbour, update and queue it!
        String key = nx + "," + ny;
        if (tentativeG < gCosts.getOrDefault(key, Integer.MAX_VALUE)) {
            gCosts.put(key, tentativeG);
            
            int heuristic = calculateManhattan(nx, ny, targetX, targetY);
            openSet.offer(new Node(nx, ny, tentativeG, heuristic));
        }
    }
}

Time Complexity

The time complexity of A* is highly dependent on the quality of the heuristic.

• Worst Case: $O((V + E) \log V)$ / $O(b^d)$ (where $b$ is the branching factor and $d$ is depth). If the heuristic is $h(n) = 0$, A* degrades exactly into Dijkstra’s Algorithm.
• Best Case: If the heuristic is physically perfect and walls don’t block the path, A* goes straight to the goal without exploring a single wrong node. Time becomes $O(d)$.

Uses in the Real World

A* is the backbone of almost all pathfinding in modern technology.

1. Video Games: Calculating how AI enemies run through a complex map to reach the player.
2. GPS Navigation: Finding the fastest driving route (using expected road speeds as the heuristic).
3. Robotics: Guiding Roombas and automated warehouse robots around obstacles.

Practice Problem

A* is rarely directly tested in standard coding interviews because of the length of the code required to set up the nodes and heaps. However, variations exist.

1. Shortest Path in Binary Matrix – LeetCode #1091 — Try solving this with classic BFS first. Then, implement the A* structure using Euclidean distance as the heuristic and compare how many fewer nodes you process!

What’s Next?

We have just one post remaining in our definitive Algorithms series. We finish with a beautiful, highly-specialised tree structure used for searching massive strings instantly: Tries (Prefix Trees).