A* shortest path

Dijkstra with a sense of direction — a heuristic steers the search toward the goal, so it explores a fraction of the graph for the same optimal answer.

Complexity: O((V + E) log V) time · O(V) space — the same worst case as Dijkstra, far better in practice with a good heuristic.

The idea

A* orders its frontier by f(n) = g(n) + h(n): g is the real cost from the start to n, and h estimates the cost from n on to the goal. Dijkstra is just A* with h = 0 — it grows outward equally in every direction. Add a heuristic that points at the goal and the frontier stops wandering: it always expands the node that looks most promising toward the destination.

The heuristic makes or breaks it

h must never overestimate the true remaining cost — an admissible heuristic. When it holds, the first time A* settles the goal that route is optimal, exactly like Dijkstra. On a map the natural choice is straight-line (Euclidean) distance: as the crow flies is never longer than any real path. graph.getPosition(node) gives each node's (x, y) to measure it. If the estimate ever runs high, A* can return a slightly suboptimal path — the price of the speed-up.

Watch for it on the canvas

Run it on the map and watch the visited region reach toward the goal in a narrow tongue instead of flooding outward the way Dijkstra does — same path, far fewer nodes touched. The bigger the graph, the wider that gap.

Try it on this map:

# A* shortest path — Dijkstra steered toward the goal by a straight-line
# heuristic, so it explores far fewer nodes. Node positions come from
# graph.getPosition(); edge weights from graph.getWeight() (1 when unweighted).
import heapq

nodes = list(graph.getNodes())
start, goal = nodes[0], nodes[-1]   # first and last node — change as you like


def heuristic(node):
    # straight-line (Euclidean) distance to the goal — never overestimates the
    # real cost when weights are distances, which is what keeps A* correct
    x1, y1 = graph.getPosition(node)
    x2, y2 = graph.getPosition(goal)
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


g = {node: float("inf") for node in nodes}   # best cost found to each node
prev = {node: None for node in nodes}
g[start] = 0
# the heap is ordered by f = g + h (estimated total trip through the node)
heap = [(heuristic(start), start)]
seen = set()

while heap:
    _, node = heapq.heappop(heap)
    if node in seen:
        continue
    seen.add(node)
    if node == goal:
        break
    for neighbour in graph.getNeighbors(node):
        if neighbour in seen:
            continue
        tentative = g[node] + graph.getWeight(node, neighbour)
        if tentative < g[neighbour]:
            g[neighbour] = tentative
            prev[neighbour] = node
            heapq.heappush(heap, (tentative + heuristic(neighbour), neighbour))

path = []
node = goal
while node is not None:
    path.append(node)
    node = prev[node]
path.reverse()

if path and path[0] == start:
    print(f"cost {start} -> {goal}: {g[goal]:.0f}")
    print("path:", " -> ".join(path))
    graph.markPath(path)
else:
    print(f"no route from {start} to {goal}")

Then run the very same code on a much larger map and see how little of it A* even looks at:

Open this post in a project to run it and step through the search.