This lesson's interactive features are locked, please to keep using them
A* Search Algorithm
Click to play video
We built the TrafficGrid and (in the previous chapter) the PriorityQueue so that we can use them in our implementation of the A* search algorithm, an optimized extension of Dijkstra's algorithm.
Why Use A*?
The A* algorithm, pronounced "A-star," is one of the best and most popular techniques used in path-finding.
Unlike conventional traversal algorithms like Dijkstra's and Bellman-Ford, A* is a "smart" algorithm that differentiates itself through the use of heuristics.
Real-World Applications
Many video games and web-based maps use A* to find approximate shortest paths very efficiently.
What Is a Heuristic?
Heuristics in computer science and artificial intelligence are "rules of thumb" used in algorithms to help them quickly find optimal solutions to complex problems.
With a good heuristic, A* can work efficiently while still guaranteeing 100% accuracy – but a bad heuristic could result in a suboptimal solution.