A* Search

Why Dijkstra Searches Behind Its Own Back

Uninformed Dijkstra’s algorithm orders the frontier strictly by g(n) — the distance traveled from Start so far. On an open warehouse floor, a step backward (cost = 1) looks just as promising to Dijkstra as a step straight toward Goal (cost = 1), so its frontier expands outward in concentric rings in every direction.

A* Search keeps Dijkstra’s exact distance table best[cell] = g(n), while ranking frontier entries in the priority queue by estimated total route cost:

f(n) = g(n) + h(n)

• g(n): Exact cost paid from Start to n.
• h(n): Heuristic estimate of the minimum cost still needed from n to Goal.
• f(n): Best-case total cost of a complete path passing through n.

On a 4-directional grid with unit step cost, Manhattan distance (|x₁ − x₂| + |y₁ − y₂|) counts the exact number of horizontal and vertical moves needed if no walls stood in the way. Moving toward the goal increases g by +1 and shrinks h by −1, keeping f flat (4 = 1 + 3 = 2 + 2), whereas stepping away from the goal increases both g (+1) and h (+1), penalizing f by +2!

The Golden Rule: Admissibility (h(n) ≤ h*(n))

Why doesn’t chasing a heuristic trick A* into returning a longer detour around a wall?

Because Manhattan distance on a 4-way grid is admissible: walls can force a path to take more moves, never fewer moves than ignoring walls (h(n) ≤ true_remaining_cost).

Suppose Goal sits at the top of the min-heap with f(Goal) = g(Goal) + 0 = 6. Every other waiting cell x in the heap has:

true_cost_via(x) ≥ g(x) + h(x) = f(x) ≥ f(Goal) = 6

No unexplored state in the frontier can possibly finish in fewer than 6 moves. Just like Dijkstra, stopping when Goal is popped guarantees a shortest path!

What if h(n) overestimates? If you use Manhattan distance on an 8-directional grid where diagonal moves cost 1, |dx| + |dy| can return 2 for a single diagonal step — overestimating the true cost and potentially missing the optimal diagonal shortcut. Match your heuristic to allowed moves:

• 4-way grid: Manhattan |dx| + |dy|
• 8-way unit grid: Chebyshev max(|dx|, |dy|)
• Continuous 2-D plane: Euclidean hypot(dx, dy)

Reference Python Implementation

Notice how our tuple (f, h, g, cell) breaks f-score ties using smaller h first. When five open paths all share f = 4, preferring the cell closest to the goal marches straight to the target instead of fanning across equal-cost diagonals:

from heapq import heappop, heappush
from math import inf


def manhattan(cell: tuple[int, int], goal: tuple[int, int]) -> int:
    return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])


def neighbors(grid: tuple[str, ...], cell: tuple[int, int]):
    x, y = cell
    for nx, ny in ((x + 1, y), (x, y - 1), (x, y + 1), (x - 1, y)):
        if 0 <= ny < len(grid) and 0 <= nx < len(grid[0]) and grid[ny][nx] == ".":
            yield (nx, ny)


def build_path(parent: dict, goal: tuple[int, int]) -> list[tuple[int, int]]:
    path = [goal]
    while path[-1] in parent:
        path.append(parent[path[-1]])
    return path[::-1]


def a_star(
    grid: tuple[str, ...],
    start: tuple[int, int],
    goal: tuple[int, int],
) -> list[tuple[int, int]] | None:
    best = {start: 0}
    parent = {}
    remaining = manhattan(start, goal)
    frontier = [(remaining, remaining, 0, start)]

    while frontier:
        _, _, cost, cell = heappop(frontier)
        if cost != best[cell]:
            continue
        if cell == goal:
            return build_path(parent, goal)

        for nxt in neighbors(grid, cell):
            candidate = cost + 1
            if candidate < best.get(nxt, inf):
                best[nxt] = candidate
                parent[nxt] = cell
                rem = manhattan(nxt, goal)
                heappush(frontier, (candidate + rem, rem, candidate, nxt))

    return None

Beyond Maps: A* on Sliding Puzzles & State Graphs

In our companion Question Bank walkthrough — Sliding Tile Puzzle (/questions/sliding-puzzle) — a “node” is no longer an (x, y) square: it is an immutable snapshot of the entire puzzle board (such as (1, 2, 3, 5, 0, 6, 4, 7, 8)). Each legal tile slide into the blank 0 slot is a weight-1 edge, and summing the Manhattan distance of every numbered tile (1..8, excluding 0) to its home square yields an admissible heuristic because each move shifts only one tile by 1 cell.