Shortest path on a graph where distances change dynamically? (maximum energy path)

Question

I'm trying to find the shortest path between two maxima on a discrete energy landscape whereby the shortest path is that which reduces the least in height over the course of the total path. Probably maximum energy path is more correct terminology, but in other words even if a path travels a long distance around the landscape but does not go down into the valleys it would be considered good.

My initial idea was to create a graph of the landscape whereby the weight was the difference in landscape height between neighbours, either positive of negative for ascent and descent respectively. I have just realised that this will not give the result I need, and actually all paths between local maxima will have exactly the same cost.

I then realised that if the distance between nodes on this graph depended on the current position and history of the path, then I could get the result I need. e.g. if the path has gone down and up from a valley, then I would assign no extra cost to going down another valley (as long as the path isn't exceeding lows it hasn't been to before).

So are there graph search algorithms that exist where the the distance can change dynamically as paths are explored?

Or are there any other suggestions for attacking this problem?

Answer 1

This is known as the Bottleneck Shortest Path problem. It is in fact easier than the Shortest Path problem, and can be solved in linear time on undirected graphs. See for example here.

Answer 2

Idea

I suggest an algorithm that builds an auxiliary tree (T) in which each node contains a list of vertices. Each subtree will contain a set of vertices that are separated from the rest of the graph by a valley. To find the distance between any two nodes, one would simply have to find their lowest common ancestor in the tree.

Algorithm

Initialization:

1. Sort the vertices ascending by height (space: O(V), time: O(V log V))
2. Let T consist only of a root node r

MakeTree(G, r):

1. Take the lowest vertex in the graph G, remove it from graph and add to the list in the root r (time cost per vertex: O(1 + E/V))
2. Repeat the above step as long as the graph is connected
3. For each connected component G' of the graph G:
   1. create a new node n in T, attach the node as a child of the root
   2. recursively run MakeTree(G', n)

Now you've got a tree with such a property that if you want to go from vertex A to B, your maximum energy path will lead through the highest of the vertices stored in the lowest common ancestor of A and B. In order to find the distance, simply find the lowest common ancestor and take the highest vertex C stored there and calculate max(abs(h(A) - h(C)), abs(h(B) - h(C))).

Example

Below is a sample graph and the corresponding tree (for the sake of brevity, vertex labels are their heights). For example, if you want to go from 22 to 14, you have to pass through 10 (the highest vertex in the lowest common ancestor in the tree, distance = 22 - 10). If you want to go from 22 to 20, you have to pass through 13 (distance = 22 - 13).