Search & Problem SolvingAdvanced⏱ 12 min06 / 14

A* Search

Learn how A* search finds the shortest path intelligently by combining real path cost with a heuristic guess — exploring only the most promising routes.

Your GPS calculates a route from your driveway to a hotel across the country in under a second. The road network has millions of intersections — so how does it avoid checking every single one? The secret is that a smart search doesn't wander blindly. It looks at where it still needs to go and uses that guess to decide where to explore next.

That idea is the heart of *A search** (pronounced "A-star"). It is one of the most elegant algorithms in all of computer science, and it powers everything from GPS navigation to video-game pathfinding to robot motion planning.

#The Problem: Finding the Best Path

Imagine a map as a graph: cities are nodes and roads are edges with a travel cost (distance, time, or fuel). We start at node S and want to reach goal node G along the cheapest possible route.

Naive approaches do one of two things badly: - Breadth-First Search (BFS) ignores costs entirely — it just counts hops, finding the fewest stops rather than the cheapest route. - Dijkstra's algorithm tracks real costs and always finds the optimal path, but it expands in all directions like a growing bubble — it has no idea which way the goal is.

A fixes Dijkstra's blindness by adding a heuristic: a quick, cheap estimate of how far each node still is from the goal. With that extra hint, A beelines toward promising territory instead of wasting time going in the wrong direction.

Think of it like

A Hiking Analogy

You're hiking through mountains and need to reach a hut you can see in the distance. Two strategies:

Dijkstra (no heuristic): You methodically explore every trail from your current spot, always choosing the lowest total distance travelled so far — even if it heads away from the hut.

*A (with heuristic):** You do the same, BUT you also glance at the hut each time and add your rough straight-line distance to it. Trails heading vaguely toward the hut get priority. You converge on the hut much faster while still guaranteeing the shortest total path.

#The Scoring Formula: f = g + h

Every node gets a single score that drives the algorithm's decisions:

g(n) — the actual cost of the path found so far from the start to node n. This is the part Dijkstra tracks.
h(n) — the heuristic estimate of the remaining cost from node n to the goal. For grid maps, Manhattan distance (steps left/right + steps up/down) works well; for geographic maps, straight-line distance is the classic choice.
f(n) = g(n) + h(n) — the total estimated cost of the cheapest solution passing through n.

At every step, A expands the node with the lowest f score. A heuristic h(n) is admissible if it never overestimates the true remaining cost — think of it as an optimistic guess. With an admissible heuristic, A is guaranteed to find the optimal path. Straight-line distance is always admissible for road maps because no real route can be shorter than the crow-flies distance.

*Dijkstra is just A with h = 0.* Set h to zero everywhere and f(n) = g(n) — the two algorithms become identical. The heuristic is the only addition A makes.

Common mistake

Inadmissible heuristics break the optimality guarantee

If h(n) overestimates the true remaining cost, A* can prematurely rule out the actual optimal path — making it look expensive — and return a suboptimal answer. A heuristic that is tight (close to the true cost) and cheap to compute is the sweet spot. Straight-line distance hits both marks, which is why it's the go-to choice.

#A* Step by Step

Here is the algorithm spelled out mechanically:

Create an open set (nodes to explore), starting with just the start node. Track each node's g score (start = 0, all others = infinity).
Pick the node in the open set with the lowest f = g + h score. Call it current.
If current is the goal, reconstruct the path by following came_from pointers back to the start — done.
Otherwise, for each neighbour of current, compute tentative_g = g(current) + cost(current, neighbour). If tentative_g is lower than the neighbour's known g score, update came_from, g, and add the neighbour to the open set.
Repeat from step 2. If the open set empties with no solution found, no path exists.

Using a min-heap (Python's heapq) to track the open set means "find lowest f" costs O(log n) instead of O(n) for a plain list — essential for large graphs.

A* on a 5x5 grid with walls (1). The algorithm navigates around obstacles and returns the shortest passable path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40import heapq

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

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_set = [(0, start)]   # (f_score, node)
    came_from = {}
    g = {start: 0}

    while open_set:
        _, 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 list(reversed(path))
        r, c = current
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nb = (r+dr, c+dc)
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != 1:
                new_g = g[current] + 1
                if new_g < g.get(nb, float('inf')):
                    came_from[nb] = current
                    g[nb] = new_g
                    heapq.heappush(open_set, (new_g + heuristic(nb, goal), nb))
    return None

# 0 = open, 1 = wall
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],
]
print(astar(grid, (0, 0), (4, 4)))

#Heuristic vs No Heuristic: A Live Comparison

Same grid, same optimal path, same algorithm — the only difference is h. Dijkstra visits every cell; A* reaches the goal after just 19. A* is everywhere once you look for it: **GPS navigation** uses A* variants to route across continent-scale networks in milliseconds; **video game NPCs** run A* to navigate maps; **robot arms** plan collision-free motion with it; **puzzle solvers** (8-puzzle, 15-puzzle) use it with a Manhattan-distance heuristic. In production Python, `networkx.astar_path()` provides a battle-tested A* for general graphs — but as you've seen, a working version needs only `heapq`.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26import heapq

def count_explored(grid, start, goal, use_heuristic=True):
    rows, cols = len(grid), len(grid[0])
    open_set = [(0, start)]
    g = {start: 0}
    explored = 0
    while open_set:
        _, current = heapq.heappop(open_set)
        explored += 1
        if current == goal:
            return explored
        r, c = current
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nb = (r+dr, c+dc)
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != 1:
                new_g = g[current] + 1
                if new_g < g.get(nb, float('inf')):
                    g[nb] = new_g
                    h = (abs(nb[0]-goal[0]) + abs(nb[1]-goal[1])) if use_heuristic else 0
                    heapq.heappush(open_set, (new_g + h, nb))
    return explored

grid = [[0]*10 for _ in range(10)]  # open 10x10, no walls
print("Dijkstra explored:", count_explored(grid, (0,0), (9,9), use_heuristic=False))
print("A* explored:      ", count_explored(grid, (0,0), (9,9), use_heuristic=True))

Quick check

You run A* on a map where your heuristic h(n) sometimes returns values *larger* than the true remaining distance to the goal. What can you conclude?

Tip

The interactive visualizer on this page

The visualizer lets you draw walls on a grid, place a start and goal, and watch A* expand nodes in real time. Notice how the frontier leans toward the goal rather than flooding outward — that's the heuristic at work. Try switching to Dijkstra mode (h = 0) and compare the two frontiers side by side.

Key takeaways

A* scores every node as f = g + h, where g is the real cost from the start and h is a heuristic estimate of the remaining cost to the goal.
Expanding the lowest-f node first makes A* explore the most promising routes before wasting time on unlikely ones.
A heuristic is admissible if it never overestimates — admissibility is the guarantee that A* finds the optimal path.
Dijkstra's algorithm is just A* with h = 0; the heuristic is the only addition and can be removed gracefully.
On large graphs, a good heuristic can cut nodes explored from millions to thousands while still guaranteeing optimality.

Try it yourself · A* pathfinding

See how a heuristic makes A* beeline for the goal vs. blind search.

algorithm:explored 1

BFS explores evenly in all directions (a queue) — it always finds the shortest path.

searching…

Practice challenges

Test yourself · earn XP

0/4

Predict the output#1

In A*, each node's priority is f = g + h. Here g is the real cost from the start and h is the Manhattan-distance heuristic to the goal. What does this snippet print?

predict-output

1
2
3
4
5
6
7
8def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])  # Manhattan distance

node = (1, 2)
goal = (4, 4)
g = 3            # real cost from start to node
h = heuristic(node, goal)
print(g + h)

Fix the bug#2

This code has a bug — what's wrong? It pushes the wrong priority into the min-heap when adding a neighbour to the open set.

fix-bug

1
2
3
4
5
6new_g = g[current] + 1
if new_g < g.get(nb, float('inf')):
    came_from[nb] = current
    g[nb] = new_g
    # push (priority, node) onto the min-heap
    heapq.heappush(open_set, (new_g, nb))

Fill in the blank#3

Complete the admissibility rule from the lesson. A heuristic is admissible if it never ______ the true remaining cost — an optimistic guess that guarantees A* finds the optimal path.

# A heuristic h(n) is admissible if it never 
# the true remaining cost to the goal.
admissible = h_estimate <= true_remaining_cost

Reorder the lines#4

Put the lines of reconstruct_path in the correct order. It walks came_from pointers from the goal back to the start, then returns the path in start-to-goal order.

path.reverse()

    path.append(current)

current = goal

path.append(start)

while current != start:

    current = came_from[current]

Your turn

Practice exercise

Implement the missing reconstruct_path function that A* calls when it reaches the goal. It receives a came_from dictionary of {node: parent_node} pointers and should return the full list of nodes from start to goal. Run the completed code to print every step of the path through the maze below.

Grid (0 = open, 1 = wall): `` [[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0]] `` Start: (0, 0) Goal: (4, 4)

Try it live — edit the code and hit Run to execute real Python:

solution.py · editable

import heapq

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

def reconstruct_path(came_from, start, goal):
    # TODO: walk came_from pointers from goal back to start,
    # collect the nodes, and return them in start-to-goal order.
    pass

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_set = [(0, start)]
    came_from = {}
    g = {start: 0}
    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return reconstruct_path(came_from, start, goal)
        r, c = current
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nb = (r+dr, c+dc)
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != 1:
                new_g = g[current] + 1
                if new_g < g.get(nb, float('inf')):
                    came_from[nb] = current
                    g[nb] = new_g
                    heapq.heappush(open_set, (new_g + heuristic(nb, goal), nb))
    return None

grid = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
]
path = astar(grid, (0, 0), (4, 4))
if path:
    for step, node in enumerate(path):
        print(f"Step {step}: row {node[0]}, col {node[1]}")
else:
    print("No path found")

import heapq

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

def reconstruct_path(came_from, start, goal):
    # TODO: walk came_from pointers from goal back to start,
    # collect the nodes, and return them in start-to-goal order.
    pass

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_set = [(0, start)]
    came_from = {}
    g = {start: 0}
    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return reconstruct_path(came_from, start, goal)
        r, c = current
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nb = (r+dr, c+dc)
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != 1:
                new_g = g[current] + 1
                if new_g < g.get(nb, float('inf')):
                    came_from[nb] = current
                    g[nb] = new_g
                    heapq.heappush(open_set, (new_g + heuristic(nb, goal), nb))
    return None

grid = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
]
path = astar(grid, (0, 0), (4, 4))
if path:
    for step, node in enumerate(path):
        print(f"Step {step}: row {node[0]}, col {node[1]}")
else:
    print("No path found")