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:
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
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.
Now, instead of returning the sum of the squared distances, return the square root of the sum of the squared distances.
Call a_star() on the euclidean_graph to find the best flight path between Jaipur and Bengaluru and print the result!