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!
target as the final parameter for
Make sure to run this code before moving onto the next checkpoint.
Rename ALL instances of
paths_and_distances. We’ll use this variable to keep track of each path too now.
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.)