You’ve built out the A* algorithm in Python! Congratulations! This is an enormous feat.
To create the oft-used algorithm you:
- Modified Dijkstra’s algorithm to include a path and target.
- Added the Manhattan heuristic to use for estimating distance on a grid.
- Changed the Manhattan heuristic to the Euclidean heuristic to estimate distances between cities.
Play around with A* in the code editor!
If you tab over to manhattan_graph.py and euclidean_graph.py, you’ll see all of the vertices you can use as origins and destinations. (Make sure to import any vertex you plan on working with in script.py.) We’ve included both heuristics in script.py for you to use.
- Try getting from one city in India to another using the Euclidean heuristic and each city’s latitude and longitude.
- What happens if you go from Herald Square to the Empire State building in Manhattan?