Graph Algorithm to Find Shortest Path Using Elevations

Question

Consider a Grid (X by Y). Each point in the grid has a value Z. Now, in this grid there are an i number of designated checkpoints. Consider the grid to have a rating D. This value D means that you can get from any of the checkpoints to another by only having to cross a path that has maximal value D. The length of a path is determined by the maximum elevation difference between two consecutive nodes taken in that path. For example consider a grid of elevations:

1 1 1 1 1  
2 1 3 1 2                                                               
1 2 3 1 2                                                              

If I take this path: (X means went on, O means didn't cross):

X X X O O
O O X O O
O O X X X

The value of this path would be 2, as the highest elevation difference was at the part where you go from 1 to 3.

The problem is thus: Find the minimal value of D that allows to get from any checkpoint to another, this means that D will be maximal length of a path from one checkpoint to another.

For example if D is 2, that means I can get from checkpoint to another by having all my paths having a maximum value of 2.

What is an efficient algorithm for this?

Answer 1

This is very much like Dijkstra's algorithm. Start at a node and explore all nodes within an increasing distance. Start with set S as any node, just the first node, and label the rest of the nodes with distance infinity. Consider unexplored edges leading out of S, and label adjacent unexplored nodes with the elevation difference if it is less than their label. Add all the adjacent nodes of minimum distance to S and repeat. The running time should be just O(E).

Answer 2

It looks like you're asking for an all-pairs shortest path solution to one of these grids. Wikipedia suggests ( http://en.m.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths ) that Floyd-Warshall (O(v^3)) or Johnson's algorithm (O(VE + V^2 log V)) would be a good choice. Since the number of edges is less than 4*V, Johnson's algorithm will be asymptotically faster.