Embed Notice

While Dijkstra's Algorithm is guaranteed to give us an optimal path (as long as no weights are negative), it considers obviously-wrong paths. As long as the path is shorter than its final answer its considered... Which suggests there's a faster way!

So A* routing adds a decent under-estimate (a road network would use the Euclidean Distance, as the crow flies) of the final cost to steer the routing algorithm in the right direction.

UIs will want to reformat the resulting answer.

2/2 Fin!