Defining the heuristics for A*

The choice of the heuristic function is important. If we set h(n) = 0 for all nodes, the A* algorithm is equivalent to Dijkstra's algorithm and we will see no performance improvement. If h(n) is too far away from the real distance, the algorithm runs the risk of not finding the real shortest path. The choice of the heuristic is then a matter of balance between speed and accuracy.

Since choosing h(n)=0 is equivalent to Dijkstra's algorithm, the A* algorithm is a variant of Dijkstra. It means it suffers from the same constraints regarding the positivity of the weights.

Within the GDS plugin, the implemented heuristic uses the haversine equation. This is a formula to compute the distance between two points on the Earth's surface, given their latitude and longitude. It corresponds to the great circle distance, as illustrated in the following:

The guess function ignores the exact shape of the network but is able to say that, to go from A to B...