liveBook · Manning

Chapter 12: A* Algorithm

What you will learn in chapter 12 of Algorithms Every Programmer Should Know

The introduction frames A* as a way to find the cheapest route to a specific destination while using an estimate of the remaining distance to guide the search.

After this chapter you will be able to

What it builds on

Section by section

Introduction

The introduction frames A* as a way to find the cheapest route to a specific destination while using an estimate of the remaining distance to guide the search.

Key terms: start point, destination, cheapest, maximal clique, A*, Dijkstra's algorithm, Floyd-Warshall algorithm, educated guess, cheapest path

12.1 What is an informed search algorithm?

This section explains how A* combines a goal-directed heuristic with actual path costs, then traces how it updates routes and decides when to stop.

Key terms: informed search, Dijkstra, heuristic, h(n), admissible, straight-line distance, Manhattan Distance, g(n), f(n), greedy best-first search

12.2 Real-world applications

The section shows how A*’s heuristic-guided search is applied to road routing, game pathfinding, and sliding-tile puzzles.

Key terms: Shakey, ALT, landmarks, triangle inequality, admissible heuristic, weighted graph, grid, navigation mesh, Manhattan distance, g(n)

12.3 Key insights

This section explains when A* is efficient, where its time and memory limits arise, and when alternative searches better fit the problem.

Key terms: A*, Dijkstra’s algorithm, heuristic, binary priority queue, O((V+E)logV), graph density, sparse graph, dense graph, tight heuristic, ALT-style landmarks

12.4 Summary

12.5 References

This section lists an A* code implementation and references for further reading.

Concepts explained in this chapter

← Chapter 11: Bron-Kerbosch Algorithm

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.