10.11 Accelerating Search with A

Dijkstra's algorithm finds shortest paths by expanding vertices in order of increasing distance from the source. This guarantees correctness, but it often explores large portions of the graph that are irrelevant to the final answer.

Suppose you want driving directions from one city to another. Dijkstra expands outward in every direction, including areas that move away from the destination. Many of those vertices will never appear in the final route.

A* addresses this inefficiency by introducing a heuristic estimate of the remaining distance to the goal. Instead of asking:

Which vertex is closest to the start?

A* asks:

Which vertex appears closest to the goal when both traveled distance and estimated remaining distance are considered?

When the heuristic is chosen carefully, A* can dramatically reduce the amount of search while preserving optimality.

Problem

Given a weighted graph, a source vertex, and a target vertex, find the shortest path between them while minimizing unnecessary exploration.

Consider a grid:

S . . . .
. # # # .
. . . # .
. # . . .
. . . . G

Where:

S is the start
G is the goal
# represents obstacles

A shortest-path algorithm should reach the goal without exploring every reachable cell.

Solution

A* extends Dijkstra by introducing a heuristic function:

h(v)

which estimates the remaining cost from vertex v to the goal.

The priority becomes:

f(v) = g(v) + h(v)

where:

g(v) is the known distance from the source
h(v) is the estimated distance to the goal

Vertices are expanded according to:

smallest f(v)

rather than smallest g(v).

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	To     int
	Weight int
}

type Item struct {
	Vertex int
	G      int
	F      int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].F < pq[j].F
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
	*pq = append(*pq, x.(Item))
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)

	item := old[n-1]
	*pq = old[:n-1]

	return item
}

func aStar(
	graph [][]Edge,
	source int,
	target int,
	heuristic func(int) int,
) int {

	const INF = int(1e18)

	dist := make([]int, len(graph))

	for i := range dist {
		dist[i] = INF
	}

	dist[source] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, Item{
		Vertex: source,
		G:      0,
		F:      heuristic(source),
	})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(Item)

		if current.Vertex == target {
			return current.G
		}

		if current.G != dist[current.Vertex] {
			continue
		}

		for _, edge := range graph[current.Vertex] {
			candidate := current.G + edge.Weight

			if candidate >= dist[edge.To] {
				continue
			}

			dist[edge.To] = candidate

			heap.Push(pq, Item{
				Vertex: edge.To,
				G:      candidate,
				F:      candidate + heuristic(edge.To),
			})
		}
	}

	return -1
}

func main() {
	fmt.Println("A* example")
}

The implementation differs from Dijkstra in only one place:

F = G + heuristic

Everything else remains familiar.

Understanding the Evaluation Function

A* combines two pieces of information.

Distance Already Traveled

g(v)

This is the exact cost from the source to v.

Estimated Distance Remaining

h(v)

This predicts the cost from v to the goal.

Combined:

f(v) = g(v) + h(v)

The search prefers vertices that appear promising.

Suppose:

Vertex	g(v)	h(v)	f(v)
A	5	20	25
B	10	5	15
C	8	10	18

A* chooses:

even though its traveled distance is larger.

The reason is that B appears closer to the goal.

Choosing a Heuristic

The heuristic determines the quality of the search.

A perfect heuristic would know the exact remaining distance.

h(v) = actual distance to goal

In that case, A* would explore only optimal paths.

Of course, if we already knew the exact remaining distance, we would not need A*.

The goal is therefore to find a cheap approximation.

Manhattan Distance

For grid movement in four directions:

|x₁ - x₂| + |y₁ - y₂|

This is often the preferred heuristic.

Euclidean Distance

For unrestricted geometric movement:

√((x₁ - x₂)² + (y₁ - y₂)²)

This estimates straight-line travel.

Domain-Specific Estimates

Road networks may use geographic coordinates.

Game maps may use movement costs.

Logistics systems may use travel-time estimates.

The better the estimate, the less unnecessary search occurs.

Admissible Heuristics

A* remains optimal only if the heuristic never overestimates the true remaining distance.

Formally:

h(v) ≤ actual remaining cost

Such heuristics are called admissible.

Suppose the actual remaining cost is:

These are admissible:

This is not:

because it exceeds reality.

Overestimation may cause A* to ignore the optimal path.

Consistent Heuristics

An even stronger property is consistency.

For every edge:

u -> v

with weight:

the heuristic satisfies:

h(u) ≤ w + h(v)

This resembles the triangle inequality.

Consistency guarantees that once a vertex is removed from the priority queue, its shortest distance is final.

Most practical geometric heuristics satisfy this property naturally.

Relationship to Dijkstra

A* becomes Dijkstra when:

h(v) = 0

for every vertex.

Then:

f(v) = g(v)

and the priority queue behaves exactly as Dijkstra's algorithm.

This observation is important.

A* is not a completely different algorithm.

It is Dijkstra augmented with guidance toward the goal.

Visualizing the Search

Suppose a grid contains:

S . . . . . G

Dijkstra expands:

S
SS
SSS
SSSS
SSSSS
...

in all directions.

A* expands roughly toward the goal:

S>>>>>>G

The difference becomes dramatic on large maps.

A* often examines a small fraction of the vertices explored by Dijkstra.

Path Reconstruction

Path reconstruction is identical to Dijkstra.

Maintain:

parent[next] = current

during relaxation.

When the target is reached, follow parent pointers backward to reconstruct the route.

The heuristic influences exploration order but does not affect reconstruction logic.

Discussion

The central idea behind A* is remarkably powerful.

Instead of exploring uniformly outward, the search incorporates knowledge about the goal.

This transforms shortest-path computation from a purely local process into a goal-directed search.

The algorithm remains exact as long as the heuristic is admissible.

This balance between optimality and efficiency explains why A* appears in so many systems.

Whenever a reasonable estimate of remaining cost exists, A* is often preferable to Dijkstra.

Complexity

Theoretical worst-case complexity remains similar to Dijkstra.

Algorithm	Worst Case
Dijkstra	O((V + E) log V)
A*	O((V + E) log V)

However, practical performance is often much better.

A strong heuristic can reduce explored vertices by orders of magnitude.

In the ideal case:

Only vertices near the optimal path are explored.

This is why A* dominates many real-world pathfinding applications.

Common Mistakes

Do not use a heuristic that overestimates actual remaining distance if optimality matters.

Do not assume any heuristic improves performance. A poor heuristic may behave almost identically to Dijkstra.

Do not spend excessive time computing the heuristic. The heuristic should be cheaper than the search it accelerates.

Do not confuse admissibility with accuracy. A heuristic may be admissible yet extremely weak.

Do not forget that A* is usually designed for a specific target. If shortest paths to every vertex are required, Dijkstra is often the better choice.

Practical Applications

A* appears in:

GPS navigation
Game AI pathfinding
Robotics
Autonomous vehicles
Warehouse automation
Route planning
Puzzle solving
State-space search

Many systems that appear intelligent are fundamentally performing heuristic shortest-path search.

Takeaway

A* extends Dijkstra by adding a heuristic estimate of the remaining distance to the goal. The priority queue orders vertices according to both the cost already incurred and the estimated cost still to come. With an admissible heuristic, A* preserves optimality while often exploring dramatically fewer vertices than Dijkstra. This combination of correctness and efficiency makes it one of the most widely used shortest-path algorithms in practice.