A* vs Dijkstra’s
- A* is an implementation Dijkstra’s with added Heuristic
- Whereas Dijkstra will determine the path cost between all nodes, A* is goal cased and its only task is to optimise the route to a goal vertex (node)
- Unlike Dijkstra, it eliminates any nodes that are not felt useful in contributing towards the goal
A* Heuristic
- The A* uses a heuristic measure to cut out the vertices that are not considered useful towards achieving the goal
- The usefulness of the A* algorithm is therefore determined by the suitability of the heuristic
- It is important that the heuristic does not overestimate the cost and choose an incorrect vertex
Example:
The Heuristic (green line) has found the geometrically closest rout from A to G, ignoring weighting at this stage.