Graph Algorithms8 min read

A* Search

Smarter than Dijkstra — use a hint to head in the right direction
time:\(O(E)\) best case, \(O((V+E)\) log V) worst caseoptimality:Guaranteed if heuristic is admissibleheuristic:h(n) ≤ actual cost to goal

Imagine you're navigating with a GPS. Dijkstra's algorithm is like a GPS that has no idea where the destination is — it expands outward in all directions equally, like ripples in a pond, until it happens to reach your destination.

A* (A-star) is a GPS that knows roughly which direction the destination is. Instead of expanding in all directions, it biases the search toward the goal using an estimate called a heuristic. The result: it reaches the destination while exploring far fewer nodes.

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

Every node n gets a priority score:

  • g(n) — the actual cost of the best known path from start to n so far
  • h(n) — the heuristic estimate of cost from n to the goal
  • f(n) = g(n) + h(n) — the estimated total cost of the cheapest path through n

The priority queue is ordered by f(n). Nodes with low estimated total cost are expanded first. This naturally steers the search toward the goal.

When h(n) = 0 for all n, f(n) = g(n), and A* reduces exactly to Dijkstra's algorithm. A* is a strict generalization.

Admissibility — The Key to Correctness

A heuristic h is admissible if it never overestimates the true cost: h(n) ≤ actual_cost(n, goal) for all n.

If h overestimates, A* may deprioritize the optimal path (thinking it's more expensive than it is) and settle on a suboptimal one. Admissibility guarantees the first time A* reaches the goal, it's via the optimal path.

Examples of admissible heuristics:

  • Manhattan distance |Δx| + |Δy| — for 4-directional grid movement
  • Euclidean distance √(Δ\(x^2\) + Δ\(y^2\)) — for free-direction movement

Consistency (Monotonicity) — Efficiency Guarantee

A stronger property: h is consistent if for every edge (n, n') with cost c, we have h(n) ≤ c + h(n'). This is the triangle inequality applied to the heuristic. Consistency implies admissibility, and additionally ensures that each node is processed only once — no re-expansions needed, just like Dijkstra.

Practical Impact

On a 1000×1000 grid, Dijkstra might explore 500,000 nodes before finding a path across. A* with Manhattan distance might explore only 5,000 — a 100× speedup. The better the heuristic (closer to the true cost without exceeding it), the fewer nodes A* explores.

When to Use A* vs. Dijkstra

Use A* when: you have a single target, and a meaningful heuristic is available. Use Dijkstra when: you need shortest paths to all destinations, or no good heuristic exists (h = 0 degenerates to Dijkstra anyway). A* is the standard algorithm in game pathfinding, GPS navigation, and robotics.

Note: The heuristic is a promise: 'I will never overestimate how far we are from the goal.' Break that promise and A* may return a suboptimal path. Keep it, and A* is both optimal and potentially much faster than Dijkstra.

A* on a Grid (Manhattan Distance Heuristic)

import heapq


def astar(grid, start, goal):
    """
    grid: 2D list, 0=free, 1=wall
    Returns shortest path length, or -1 if unreachable.
    """
    rows, cols = len(grid), len(grid[0])
    def h(r, c):  # Manhattan distance heuristic
        return abs(r - goal[0]) + abs(c - goal[1])


    dist = {start: 0}
    # heap: (f, g, node)
    heap = [(h(*start), 0, start)]


    while heap:
        f, g, (r, c) = heapq.heappop(heap)
        if (r, c) == goal:
            return g
        if g > dist.get((r, c), float('inf')):
            continue  # stale entry
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                ng = g + 1
                if ng < dist.get((nr, nc), float('inf')):
                    dist[(nr, nc)] = ng
                    heapq.heappush(heap, (ng + h(nr, nc), ng, (nr, nc)))
    return -1


grid = [
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
print(astar(grid, (0,0), (4,4)))  # 12
Output
12

Complexity

🎯 Best case (perfect heuristic)If h = exact remaining cost, A* expands only nodes on the optimal path — as good as it gets
Explores only the optimal path\(O(path length)\)
🌊 Worst case (h = 0)With no heuristic information, A* explores all directions equally like Dijkstra
Degrades to Dijkstra\(O((V+E)\) log V)
💾 SpaceOpen and closed sets can hold all vertices in the worst case
Proportional to nodes explored\(O(V)\)
✅ OptimalityInadmissible heuristics may find suboptimal paths but run faster — useful when approximate is OK
Requires admissible heuristich(n) ≤ true cost

Quick check

What does f(n) = g(n) + h(n) represent?

Continue reading

Dijkstra's Algorithm
Always extend the cheapest road first — GPS navigation for graphs
→
Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→