ZERO / HERO
Dijkstra with a compass

A* Search

The analogy

Dijkstra explores in every direction equally, like a ripple. But if you know roughly which way the destination lies, why explore backwards? A* adds a guess of the remaining distance to each candidate, so it leans towards the goal — the same guarantee, a fraction of the exploration.

Visualizer

Dijkstra with a compass

step 1 / 10
r0
r1█G
r2██
r3██
r4S█
r5

A grid. S is the start, G the goal, black cells are walls. Both Dijkstra and A* will find the same optimal path — the difference is how much they explore.grid 6x9, 4-directional movement

import heapq

def astar(start, goal, neighbours, h):
    g = {start: 0}
    pq = [(h(start), 0, start)]
    parent = {}
    while pq:
        f, gu, u = heapq.heappop(pq)
        if u == goal:
            return gu, parent
        if gu > g.get(u, float("inf")):
            continue
        for v, w in neighbours(u):
            ng = gu + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h(v), ng, v))
    return None, parent

# 4-dir grid: h = abs(dx) + abs(dy)      (Manhattan)
# 8-dir grid: h = octile distance
# h = 0  ->  this IS Dijkstra
Check yourself

Your heuristic sometimes OVERestimates the remaining distance. Consequence?