A* Search

Graphs O(E) O(V)

Best-first shortest path guided by a heuristic: expands the node with the lowest g + straight-line estimate.

Start

Goal

1/32

Goal is 5. g[0] = 0, f[0] = h = 32.

InvariantFor a closed node, g is final. That needs h never to overestimate the remaining distance.

currentfrontiervisitedtree edge

a-star.c

#define V 6
#define INF 1000000
 
/* h[v] = straight-line estimate from v to the goal */
int aStar(int graph[V][V], int h[V], int src, int goal) {
    int g[V], f[V], closed[V] = {0};
    for (int i = 0; i < V; i++) { g[i] = INF; f[i] = INF; }
    g[src] = 0;
    f[src] = h[src];
 
    for (int count = 0; count < V; count++) {
        int u = -1;
        for (int v = 0; v < V; v++)
            if (!closed[v] && (u == -1 || f[v] < f[u]))
                u = v;
        if (u == goal) return g[goal];
        closed[u] = 1;
 
        for (int v = 0; v < V; v++)
            if (graph[u][v] && g[u] + graph[u][v] < g[v]) {
                g[v] = g[u] + graph[u][v];
                f[v] = g[v] + h[v];
            }
    }
    return -1;
}

How A* Search works

Dijkstra with a sense of direction: order the frontier by g(n) + h(n), the cost so far plus an optimistic estimate to the goal. With an admissible h it never overlooks a shorter path, yet ignores most of the graph.

Best case

Perfect heuristic — expands only the optimal path's nodes.

Worst case

h ≡ 0 degenerates to plain Dijkstra.

When to use it

Pathfinding with a geometric goal: games, robotics, maps (straight-line distance as h).