**Essential algorithms for GCSE and A Level Computer Science**

**Optimisation algorithms**

Routines that find satisfactory or optimum paths between vertices / nodes on a graph.

**What is A* pathfinding?**

The A* pathfinding algorithm is a development of Dijkstra’s shortest path. Unlike Dijkstra’s algorithm, A* finds the shortest path between two vertices on a weighted graph using heuristics. It performs better than Dijkstra’s algorithm because not every vertex is considered. Instead, only the most optimal path is followed to the goal.

Known as a best-first search algorithm, with A* pathfinding a heuristic estimates the cost of the path between the next vertex and the goal. It then follows this path. It is important that the heuristic does not over-estimate the cost, thereby choosing an incorrect vertex to move to next. The vertices being considered are referred to as “the fringe”.

The usefulness of the A* algorithm is determined by the suitability of the heuristic.

**What extra is in the book?**

** **

This algorithm / data structure has its own dedicated chapter in the book, which includes:

- Overview
- Typical applications / uses
- Typical operations
- The algorithm written out in simple-structured English
- The algorithm written out in pseudocode
- Full code listing Python
- Full code listing in Visual Basic
- Diagrammatic walk-through
- Efficiency discussion with reference to Big-O notation

A hard copy of the book is available **on our shop** and a free PDF copy is included for all premium subscribers.