Just like Dijkstra's algorithm, this recipe uses the binary heap extracted from the GPWiki. Also, it is important to understand what delegates are and how they work. Finally, we are entering into the world of informed search; that means that we need to understand what a heuristic is and what it is for.
In a nutshell, for the purpose of this recipe, a heuristic is a function for calculating the approximate cost between two vertices in order to compare them to other alternatives and take the minimum-cost choice.
We need to make small changes to the Graph class:
- Define a member variable as a delegate:
public delegate float Heuristic(Vertex a, Vertex b);
- Implement a Euclidean distance member function to use it as a default heuristic: ...