Calculating driving directions is the most commonly used geospatial function in the world. Typically these algorithms calculate the shortest path between point A and B or they may take into account the speed limit of the road or even current traffic conditions to choose a route by drive time.
But what if your job is to build a new road? Or what if you are in charge of deciding where to run power transmission lines or water lines across a remote area? In a terrain-based setting, the shortest path might cross a difficult mountain or run through a lake. In this case we need to account for obstacles and avoid them if possible. However, if avoiding a minor obstacle takes us too far out of our way, the cost of implementing that route may be more expensive than just going over a mountain.
This type of advanced analysis is called Least Cost Path analysis. We search an area for the route that is the best compromise of distance versus the cost of following the route. The algorithm...