Consider a directed graph with each edge assigned a nonnegative weight D that reflects the difficulty of passing over that edge (perhaps modeling an obstacle course). Define the difficulty of a directed path to be the maximum of the difficulties of its edges. Give an efficient algorithm that computes a path from s (a designated vertex) to each of the other vertices, such that the path to any given vertex has minimum difficulty among all such paths.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
This problem can be solved using a minor modification of Dijkstra's algorithm. As you probably know, Dijkstra maintains three sets of vertices throughout the algorithm:
A: vertices for which the distance to s is computed
B: neighborhood of A
C: everything else
The algorithm gradually moves all vertices from C to B to A until all distances are known. The only necessary modification occurs in the move from B to A. The original algorithm does the following:
1) Find the vertex v in B which (among vertices in B) has the smallest distance to some vertex a in A.
2) Remove v from B, add v to A and set v's distance to x := d(s, a) + d(a, v) if x is smaller than the currently best distance, otherwise do not update v's distance.
3) Add potential new neighbors to B (and remove them from C).
All we need to do here is replace the sum in step 2) with a maximum and the algorithm should work for your problem.