Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
It's not quite Dijkstra's algorithm, because at least for the usual Dijkstra's algorithm, we are minimizing the sum of the weights of edges on a path, whereas for this problem, we want to minimize the maximum of the weights. –  Ted Sep 27 '11 at 4:16
    
And please double check your title for typos and mispelled famous names: it is the very first thing people will see of your question... (Waiting for some enterprising soul to do the fixeing for you is, hmm, not great) –  Mariano Suárez-Alvarez Sep 27 '11 at 4:19
2  
@Mariano: Looks like Muphry's law caught up with you ("fixeing") :-) –  Rahul Sep 27 '11 at 5:01
    
I don't care to try and find one, how much are you paying for it? Oh, that's a question you're asking? Please try and write it in question form then. (All in good spirit, I hope.) –  Asaf Karagila Sep 27 '11 at 6:46
    
This is a dynamic programming problem. If you want a path from s to t to pass through a vertex v, there is no harm in making the subpath from s to v a minimum difficulty path. So find the minimum difficulty a path can have, find all places reachable with that difficulty, then find the next lowest difficulty that can get you to a currently unvisited vertex. Continue untill you've found minimal difficulty paths everywhere. This is similar to Dijkstra's, but it is better to think in terms of ideas/concepts, not other known algorithms, if possible. –  Aaron Sep 27 '11 at 7:13
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.