In a road network graph, the nodes are represented by their coordinates (x,y) and the edges have a weight equal to the euclidean distance between the two connected nodes.
In an A* search algorithm executed over a road network graph, is the heuristic defined as the euclidean distance consistent (h(m)<=h(n)+d(m,n) for any edge (m,n))?
Yes, the Euclidean distance heuristic is consistent. This property is known as the triangle inequality
It also works on the surface of the Earth, if you use great-circle distances, even though that geometry is non-Euclidean.
Be careful to do it correctly, though -- calculating with latitude and longitude as if they were cartesian coordinates can sometimes produce the wrong answer.
