# Directed Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?

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.

-
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
@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

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.

-