Dijkstra's algorithm is thorough and blind: it expands the cheapest frontier in every direction, spending effort on regions pointing away from the goal. A* gives the search a compass. Each node is scored f(n) = g(n) + h(n), the cost actually paid to reach it plus a heuristic estimate of what remains, and the frontier expands in order of f. As long as the estimate never overshoots the true remaining cost, A* still finds the optimal path, while skipping most of the map. That property has a name, admissible, and it's the entire contract.

Set h = 0 everywhere and the score collapses to g alone: A* literally is Dijkstra without a compass. Everything else, the heap, the relaxation, the stale-entry skip, transfers between the two unchanged, which is why game engines treat them as one algorithm with a tunable sense of direction.

Watch the compass work on a 5 × 5 grid with unit steps, start at (0, 0), goal at (0, 4) on the same row, heuristic = Manhattan distance. After the first expansion, two cells sit on the frontier at the same real cost g = 1: (0, 1), one step along the row, and (1, 0), one step away from it. Dijkstra sees identical costs and no reason to prefer either. Predict the two f scores before reading on.

The on-row cell scores f = 1 + 3 = 4, three cells left to cover. The off-row cell scores f = 1 + 5 = 6, since wandering down added distance the heuristic sees immediately. A* expands the 4 strictly first, and the same logic repeats at every junction, so the search marches straight along the row and never touches the lower half of the grid. Both algorithms return the same optimal 4-step path. One of them visits a fraction of the cells.

import heapq

def a_star(grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int]) -> int:
    # 0 = open cell, 1 = wall; returns fewest steps or -1
    rows, cols = len(grid), len(grid[0])

    def heuristic(cell: tuple[int, int]) -> int:
        # Manhattan distance: the exact cost if nothing were in the way
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

    # Heap entries: (g + h, g, cell)
    best_g = {start: 0}
    heap = [(heuristic(start), 0, start)]

    while heap:
        _, g, cell = heapq.heappop(heap)

        # First pop of the goal is the optimal path
        if cell == goal:
            return g

        # Stale entry: a cheaper route to this cell already exists
        if g > best_g.get(cell, float("inf")):
            continue

        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            r, c = cell[0] + dr, cell[1] + dc

            if 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0:
                candidate = g + 1
                if candidate < best_g.get((r, c), float("inf")):
                    best_g[(r, c)] = candidate
                    heapq.heappush(heap, (candidate + heuristic((r, c)), candidate, (r, c)))

    return -1

Each movement rule has a natural exact-if-unobstructed estimate. Four-direction grids take Manhattan distance, |dx| + |dy|. Eight-direction grids take the octile formula, since a diagonal covers both coordinates at once. Free movement takes straight-line Euclidean. The pairing matters more than it looks: Manhattan on an eight-direction grid overestimates (a diagonal step closes two coordinate gaps while Manhattan charges for both), and an overestimating heuristic voids the optimality guarantee without any visible error.

You might think a bigger heuristic just means a faster search. Bigger means greedier: as h outgrows the truth, the search ignores real costs and beelines, returning paths that look fine and aren't optimal. The other direction is always safe, just slower, and the stronger property worth knowing by name is consistency, h(n) ≤ cost(n, n') + h(n') across every edge, which keeps f non-decreasing along paths and lets every node be expanded exactly once.

Dijkstra's loop with one new ingredient:

A* owns single-pair pathfinding wherever a decent estimate exists: game maps, robot navigation, puzzle solving. The puzzle case generalizes the "distance" idea nicely: for a sliding puzzle, the number of misplaced tiles never overestimates the moves remaining, and for a word ladder, the count of differing letters can't exceed the substitutions left. Any state-space BFS with a measurable gap to the goal upgrades the same way: keep the search, add the compass.

On platforms like LeetCode, A* rarely appears by name, because plain BFS or Dijkstra passes within the limits. It appears as the follow-up question instead: "how would you speed this up if the grid were a thousand times larger?" The answer they're fishing for is a heuristic and the argument that it never overshoots.

The algorithm is Dijkstra. The craft is all in the heuristic:

Two checks first: what exactly does admissible mean, and what does A* become when the heuristic returns 0 everywhere? Solve each problem below with BFS or Dijkstra first, then add a heuristic and measure what it skips: