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:

`$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.

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

### Instructions

**1.**

Go to `heuristic()`

and change the return statement so that `x_distance`

and `y_distance`

are each squared.

Make sure you run your code before moving on to the next checkpoint.

**2.**

Now, instead of returning the sum of the squared distances, return the **square root** of the sum of the squared distances.

**3.**

Call `a_star()`

on the `euclidean_graph`

to find the best flight path between Jaipur and Bengaluru and print the result!