Rather than simply checking the distance up to the current vertex, we will check the distance up to the current vertex + the estimated distance from the current vertex to the end vertex. We call this estimated distance the *heuristic*. For instance, in a graph where the vertices are cities, and the edges are roads, we can estimate the distance between two cities through a distance formula:

`$d = \sqrt {\left( {x_1 - x_2 } \right)^2 + \left( {y_1 - y_2 } \right)^2 }$`

There are only a few important changes you will need to make to Dijkstra’s algorithm to turn it into a star of an algorithm:

**Add a target for the search.**The new algorithm cannot optimize with a heuristic unless it has a clear destination.**Gather possible optimal paths and identify a single shortest path.**You want to find a path that has the shortest distance for the least cost.**Implement a heuristic that determines the likely distance remaining.**The main difference between Dijkstra’s and this new algorithm is that this one knows which direction to head in.

This new algorithm is called ** A***. It’s sometimes referred to as a

*greedy algorithm*because it makes a locally optimal choice at every vertex. The heuristic that A* uses makes it an introductory example of artificial intelligence!

In fact, going back to our train example. With A*, the search would be visualized as the following: