Not every algorithm can be A*. Turn Dijkstra's into A* in Python!

A* Algorithm: Python

Try running the code as is now and see how it does with a graph of vertices. 

Oh no! Our new `path_and_distances` values have wreaked havoc on the function! Why is this happening?

Our function is breaking when called because we went from tracking only distance to tracking distance AND a path.

Let's clean this up a bit.



Pathway to A Star-dom


There are several kinds of heuristics out there that you can use to estimate distance, but we'll start with the _Manhattan heuristic_. This heuristic is only considered _admissible_ — meaning that it never overestimates the distance in reaching the target — in a grid system in which the search can only move up, down, left, or right. 

To get the heuristic estimate, we need to:
- Measure the distance between the two vertices' `x` positional values and between their `y` positional values.
- Return the sum of the `x` distance and `y` distance together.

<img src='https://content.codecademy.com/programs/machine-learning/distance-formula/manhattan.svg' alt='Manhattan distance' width='100%'/>

A Starry-Eyed Heuristic that Never Sleeps


Not all vertices are on a grid and sometimes the shortest distance is closer to a direct diagonal line between two points. For these situations, a Manhattan heuristic would overestimate the total distance, making it _inadmissible_; the _Euclidean heuristic_ would be a better fit.

The Euclidean heuristic works off of the [Pythagorean theorem](https://en.wikipedia.org/wiki/Pythagorean_theorem):
```tex
EstimatedDistance = \sqrt{xDistance^2 + yDistance^2}
```
When you think about it, what we are finding is essentially a hypotenuse of a right triangle; the other two sides would be the x-distance and the y-distance.

<img src='https://content.codecademy.com/programs/machine-learning/distance-formula/euclidean.svg' alt='Manhattan distance' width='100%'/>

However, there are trade-offs for the more exact calculation. The Euclidean heuristic's square root calculation slows the runtime.


Are Eucliding Me, Heuristic?


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:
1. **Include a target for the search to find.** No more searching in all directions for all destinations.
2. **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.
3. **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!



A Star Is Born

So far, what you've created is a modified Dijkstra's algorithm that has a target and returns the path to that target. 

To make this algorithm truly ~~a star~~ A\*, you'll need to add a **_heuristic_** that **estimates the distance from a given vertex to the target**. 

By doing this, the algorithm is able to efficiently and accurately predict whether or not it is heading in the best possible direction.



A* to Finish with a Heuristic

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.