1. Improving perfection?

While dijkstra's shortest path algorithm is perfectly fine for finding shortest paths in small to medium-sized graphs, it is simply inadequate for large graphs. In these cases, we don't need to find the absolute most optimal path. A reasonably optimal path would suffice, therefore we can come up with some kind of metric that can measure how far a path is from achieving a goal. There are many heuristics that can be applied to solve this problem, each with different trade-offs. A common heuristic to use for path-finding is to use the euclidean distance between two nodes.

2. Hijacking Dijkstra's algorithm.

The A* Heuristics algorithm is simply an extension of Dijkstra's shortest path algorithm. As we have discussed before, Dijkstra sorts nodes based on their distance from the source node. What if we simply add our heuristic to that value? In fact, that is the core idea of A*. The algorithm attaches the heuristic weight of a node to the distance of the node, and runs dijkstra. This weight can be evaluated in many ways, for example with a heuristic function of the euclidean distance, the heuristic weight can be calculated with the pythagorean theorem. Other heuristics also exist, like using the manhattan distance.

3. What does A* look like?

A* intrinsically looks the same as Dijkstra, but with an added heuristic weight parameter. This parameter is only included in the Queue of Dijkstra, and is not actually added to the distance of each node. Here is a visual representation of the differences between dijkstra and A*:

Dijkstra is on the left, and A* is on the right.