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:

1. Add a target for the search. The new algorithm cannot optimize with a heuristic unless it has a clear destination.
2. 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.
3. 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: