Essential algorithms and data structures

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.

A* pathfinding videos

What extra is in the book?

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

  1. Overview
  2. Typical applications / uses
  3. Typical operations
  4. The algorithm written out in simple-structured English
  5. The algorithm written out in pseudocode
  6. Full code listing in Python
  7. Additional code listings in Visual Basic and C# are also available to download
  8. Diagrammatic walk-through
  9. 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.

Registered in England and Wales: 10442992

VAT Number: 290 9845 58

Telephone: 03330 164 059


BETT Finalists 2022
Teach Secondary Awards 2022 Finalist