A* Pathfinding Explained: Why It Beats Dijkstra

January 25, 2026·6 min read

If you have ever used Google Maps, played a strategy game, or watched a robot navigate a warehouse, you have seen pathfinding in action. The algorithm behind most of that is *A (A-star)**, and it is one of the most elegant ideas in computer science. It finds the shortest path between two points, just like Dijkstra's algorithm, but it does it significantly faster by being smarter about where it looks.

Check out the full video on my YouTube channel Divide and Quantum.

The Problem: Finding the Shortest Path

Given a graph (a grid, a road network, a game map) with weighted edges, find the path from a start node to a goal node that minimizes total cost. Dijkstra's algorithm solves this problem. So does A*. The difference is how much work they do along the way.

Dijkstra's algorithm explores nodes in order of their distance from the start. It expands outward in every direction, like a ripple in a pond, until it reaches the goal. This guarantees the shortest path, but it wastes time exploring nodes that are in the completely wrong direction.

A* adds a simple but powerful idea: use a heuristic to estimate how far each node is from the goal, and prioritize nodes that appear to be closer. Instead of expanding blindly in all directions, A* focuses its search toward the destination.

The Core Formula: f = g + h

Every node in A* has three values:

g(n): the actual cost from the start node to node n (same as Dijkstra)
h(n): the estimated cost from node n to the goal (the heuristic)
f(n) = g(n) + h(n): the total estimated cost of the path through node n

A* always expands the node with the lowest f(n) value. This is the key insight: by combining what we know (g) with what we estimate (h), we make much better decisions about which nodes to explore next.

Choosing a Good Heuristic

The heuristic h(n) is what makes A* fast, but it has to follow one rule to guarantee the shortest path: it must be admissible, meaning it never overestimates the true cost to the goal.

Common heuristics for grid-based pathfinding:

Manhattan distance: |x1 - x2| + |y1 - y2| — used when movement is restricted to four directions (up, down, left, right)
Euclidean distance: sqrt((x1 - x2)^2 + (y1 - y2)^2) — used when movement can go in any direction
Chebyshev distance: max(|x1 - x2|, |y1 - y2|) — used when diagonal movement costs the same as cardinal movement

If h(n) = 0 for all nodes, A* degrades into Dijkstra's algorithm. The better your heuristic, the fewer nodes A* needs to explore.

A* in Python

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

python
import heapq

def astar(grid, start, goal):
    """
    Find the shortest path on a 2D grid using A*.
    grid: 2D list where 0 = walkable, 1 = wall
    start: (row, col) tuple
    goal: (row, col) tuple
    Returns: list of (row, col) tuples representing the path
    """
    rows, cols = len(grid), len(grid[0])

    def heuristic(a, b):
        # Manhattan distance
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    open_set = []
    heapq.heappush(open_set, (0, start))

    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while open_set:
        current_f, current = heapq.heappop(open_set)

        if current == goal:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for dr, dc in directions:
            neighbor = (current[0] + dr, current[1] + dc)

            if (0 <= neighbor[0] < rows
                and 0 <= neighbor[1] < cols
                and grid[neighbor[0]][neighbor[1]] == 0):

                tentative_g = g_score[current] + 1

                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return []  # No path found

And here is how you would use it:

python
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
]

path = astar(grid, (0, 0), (4, 4))
print(path)
# [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (3, 3), (4, 3), (4, 4)]

A* vs. Dijkstra: A Direct Comparison

Let's compare the two algorithms on the same problem to see why A* wins.

Dijkstra's Approach

Dijkstra expands nodes in concentric rings outward from the start. On a 100x100 grid with the goal in the far corner, Dijkstra might visit most of the 10,000 cells before finding the path.

python
def dijkstra(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_set = []
    heapq.heappush(open_set, (0, start))

    came_from = {}
    dist = {start: 0}
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while open_set:
        current_dist, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for dr, dc in directions:
            neighbor = (current[0] + dr, current[1] + dc)
            if (0 <= neighbor[0] < rows
                and 0 <= neighbor[1] < cols
                and grid[neighbor[0]][neighbor[1]] == 0):
                new_dist = dist[current] + 1
                if new_dist < dist.get(neighbor, float('inf')):
                    dist[neighbor] = new_dist
                    came_from[neighbor] = current
                    heapq.heappush(open_set, (new_dist, neighbor))

    return []

The Performance Difference

On an open grid, A* with Manhattan distance explores nodes in a narrow corridor toward the goal. Dijkstra explores a full expanding circle. The difference is dramatic:

Scenario	Dijkstra (nodes visited)	A* (nodes visited)
50x50 open grid	~2,500	~100
100x100 with sparse walls	~8,000	~400
Maze with narrow passages	~3,000	~2,800

In open spaces, A* can be an order of magnitude faster. In tight mazes where there is only one possible path, the advantage shrinks because the heuristic cannot eliminate many options.

When A* Struggles

A* is not always the best choice.

High-Dimensional Spaces

A* keeps all visited nodes in memory. In problems with millions of possible states (like robot arm planning in 6D configuration space), the memory usage becomes prohibitive. Algorithms like RRT (Rapidly-exploring Random Trees) are often preferred.

Poor Heuristics

If your heuristic is not admissible (it overestimates), A* may not find the shortest path. If your heuristic is admissible but loose (much lower than the true cost), A* degrades toward Dijkstra-level performance.

Dynamic Environments

Standard A* assumes the graph doesn't change during search. For environments where edges change in real time (think traffic or a robot avoiding moving obstacles), variants like D* Lite are used instead.

Real-World Applications of A* Pathfinding

A* and its variants power some of the most important systems in technology:

Google Maps / Waze: Road networks are graphs. Turn-by-turn navigation uses A* variants combined with hierarchical decomposition (contraction hierarchies) for speed.
Video games: Nearly every strategy game, RPG, and simulation uses A* for NPC movement. The game industry has developed dozens of A* optimizations like Jump Point Search.
Warehouse robotics: Amazon's Kiva robots use pathfinding algorithms to navigate warehouse floors without colliding, coordinating hundreds of robots simultaneously.
Autonomous vehicles: Self-driving cars use A* variants in their motion planning stack to find collision-free paths through traffic.

Key Takeaways

A* is Dijkstra with direction. By adding a heuristic estimate of remaining distance, it focuses the search toward the goal and dramatically reduces the number of nodes explored. The formula f = g + h is simple, but its impact on performance is profound. If you ever need to find the shortest path and you know where the goal is, A* should be your first choice.