A* Algorithm

This lesson covers the A (A-star) algorithm* — a heuristic-based search algorithm that finds the shortest path more efficiently than Dijkstra's in many cases. It is part of the OCR A-Level Computer Science (H446) specification, section 2.3.

---

What is A*?

A* (pronounced "A-star") is a best-first search algorithm that finds the shortest path between a start vertex and a goal vertex by combining:

1. g(n) — the actual cost from the start to the current vertex n.
2. h(n) — a heuristic estimate of the cost from vertex n to the goal.

The algorithm selects the next vertex to explore based on:

f(n) = g(n) + h(n)

Where f(n) is the estimated total cost of the path through vertex n.

---

How A* Differs from Dijkstra's