Take a moment to peruse the code in the editor. That a_star() function may look oddly familiar… hey, wait a second, that’s Dijkstra’s algorithm!
To build out an A* implementation in Python, you’ll begin with Dijkstra’s algorithm and then build on it. This is pretty neat because it means that most of the algorithm is already built out.
There are only a few important changes you will need to make:
- Include a target for the search to find. No more searching in all directions for all destinations.
- Collect and return the shortest path. A dictionary of distances is cool and all, but A* is on a mission to get you to your target destination and tell you how to get there.
- Build a heuristic that calculates the estimated distance between two points. This is the crucial point of difference between Dijkstra’s and A*; A* has a real sense of direction.
Ready to bring A* to life? Let’s do this!
Instructions
Add target as the final parameter for a_star().
Make sure to run this code before moving onto the next checkpoint.
Rename ALL instances of distances within a_star() to paths_and_distances. We’ll use this variable to keep track of each path too now.
Inside the for vertex in graph loop, change the value mapped to vertex to a list of:
inf(This will be the distance.)- a list containing
start.name(This will be the path, starting with the first vertex.)