Description

A* is a graph search algorithm for finding the shortest path to a target. It's Dijkstra's Algorithm plus a heuristic: instead of expanding the closest node so far, it expands the node with the lowest f(n) = g(n) + h(n), where g is the cost from the start and h is an estimated cost to the target. It does this using a priority queue (Heaps) instead of the Queue used by Breadth First Search.

The heuristic must never overestimate the true remaining cost (be admissible) or the result may not be shortest. Common choices: straight-line/Euclidean distance on maps, Manhattan distance on grids.

Runtime

O(E log V) with a binary heap — same as Dijkstra; in practice much faster because the heuristic prunes exploration toward the target. With h(n) = 0 it is Dijkstra.

Pseudocode

Add the start node to a priority queue with priority g + h
While there is a value in the queue
    Pop the node with the lowest f = g + h
    If the node is the one we are looking for, return
    If it is not,
        Mark it as visited
        For each neighbor, if the new g is better than any previous g,
            record it and enqueue the neighbor with priority g + h
If the queue is empty and you didnt find it, there is no path to it.

Code

import heapq

def a_star(start, target, graph, h):
    g = {start: 0}
    queue = [(h(start), start)]  # (f, node)

    while queue:
        f, key = heapq.heappop(queue)
        if key == target:
            return g[key]

        for node, edge_cost in graph[key].neighbors:  # (neighbor, cost)
            new_g = g[key] + edge_cost
            if node not in g or new_g < g[node]:
                g[node] = new_g
                heapq.heappush(queue, (new_g + h(node), node))

    return -1  # target not reachable