3
$\begingroup$

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.

  • 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.2011-09-27
  • 0
    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)2011-09-27
  • 2
    @Mariano: Looks like [Muphry's law](http://en.wikipedia.org/wiki/Muphry%27s_law) caught up with you ("fixeing") :-)2011-09-27
  • 0
    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.)2011-09-27
  • 0
    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.2011-09-27

1 Answers 1