Advanced · Module 17 · Lesson 3 of 4
A* and heuristics
A* is Dijkstra's algorithm with a sense of direction: it orders vertices by distance so far plus an estimate of the distance remaining. If the estimate never overestimates, the path it finds is still optimal, usually after exploring far less.
By the end you can
- Run A* with priority g + h, and relate it to Dijkstra
- Explain admissible and consistent heuristics, and what each guarantees
- Choose heuristics for grids and maps, and recognize the trade-off of inadmissible ones
Builds on Negative edges and Bellman-Ford.
01 · A question first
Searching for a route from Paris to Berlin, Dijkstra's algorithm explores outward in every direction, including toward Madrid. A* explores mostly toward Berlin and still guarantees the shortest route. What extra information does it use, and what must be true of that information?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Searching with a sense of direction
- Admissible heuristics keep it optimal
- Heuristics for common spaces
- Measuring a heuristic's value
- Trading optimality for speed
- A* in practice
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem