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

So you don't care at all about the total path length, right? Just the minimum value that you encounter along the path?

If that's the case, then you shouldn't use "distance" in the traditional sense as your cost for Dijkstra. Your priority queue should return the node with the highest energy value - that way you're guaranteed never to take a path through a lower value if a better path exists.

I believe this is different than what @Paul Hankin is suggesting in his answer. This will probably open a lot of nodes in the graph; I think you can optimize as follows:

1. Use the [Euclidean or Manhattan] distance to the goal as a the tie-breaker in the comparison function. That way, if two nodes have equal energy, you'll try the one that gets to the goal faster.

2. When adding nodes to the priority queue, instead of using its actual energy for its "cost", use the minimum of its energy and the smallest energy encountered so far. Since you only care about the global min cost, once you're forced to take a low energy node, everything higher than that "costs" the same. This makes the search behave like a normal A* search in the neighborhood of the goal.

3. Starting search at the lower of the local maxima (I'm not positive, but I think it will be faster).

Using the distance as a tie-breaker in #1 won't affect the minimum energy, but it should make things run faster (it's sort of like an A* search).

---

Edit: here's a completely different (but probably slower) way to think about.

First, pick a threshold energy. Do a standard Dijkstra/A* search, but reject any nodes whose energy is below the threshold. If you there is no path, pick a bigger threshold and try again. A "safe" initial guess would be the minimum E along a simple path (e.g. go left then go up) from the start to the goal.

Now increase the threshold, and redo Dijkstra/A*. Keep doing so until you can't find a path. The last path before you can no longer find a path is the shortest path that has the greatest minimum energy along the path.

You also might be able to reuse the path cost from one search as an improved A* heuristic for the next search. Since increasing the threshold will only increase the length of paths, it's an admissible heuristic.

---

Hope that helps. Let me know if anything is unclear.

Answer 3

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).

                                   

Answer 4

Two possibilities.

a) In e.g. the version at http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm there is a line that works out a possibly improved distance to a point v using a route through a point u:

alt := dist[u] + dist_between(u, v)

14 if alt < dist[v]: // Relax (u,v,a)

15 dist[v] := alt

16 previous[v] := u

You seem to want a version that goes alt := K - min(height[u], height[v]). This works for much the same reason as the version with addition: at any time the set of vertices removed from Q all have the minimum cost worked out correctly for any route from the source. Each time you remove a vertex from Q, because you are removing the one with minimum distance, there is no chance of any short cut to it using the other vertices still in Q.

b) Take any method for working out if there is a route at all from the source. Use a graph which contains only point with height >= H and see if there is a solution. Try various H until you find one that just works. You can sort all the heights ahead of time and then use binary chop on this array.

Answer 5

Given the endpoints are at maxima, your problem is equivalent to this one:

For x in the graph, let h(x) be the distance below the starting point. (By the statement of the problem, all points are below the starting point).

Find the path which minimizes: max(h(x) for x in path).

You can use a variant of Dijkstra's shortest-path to solve this. I've copied and modified the description of the algorithm from wikipedia (only the distance calculation in step 3 changes).

1. Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.

2. Mark all nodes as unvisited. Set initial node as current.

3. For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and is connected to another node (B) with h(B) = 7, the distance to B through A will be max(6, 7) = 7. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.

4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next "current node" and continue from step 3.

Answer 6

Maybe the following works:

Create a graph of the landscape with the weights being dist + abs(height_a - height_b).

The abs function makes it expensive to rise or fall, and as you already noticed, the height difference alone is not enough as it is constant for any two points on the map no matter which route you go.

The dist is the plain distance (or even a constant 1 in all cases) and might be omitted, but if you like to get short paths this should favor short over long with otherwise same costs.

It's untested of course. :-)