Finding the path with the maximum minimal weight

Question

I'm trying to work out an algorithm for finding a path across a directed graph. It's not a conventional path and I can't find any references to anything like this being done already.

I want to find the path which has the maximum minimum weight.

I.e. If there are two paths with weights 10->1->10 and 2->2->2 then the second path is considered better than the first because the minimum weight (2) is greater than the minimum weight of the first (1).

If anyone can work out a way to do this, or just point me in the direction of some reference material it would be incredibly useful :)

EDIT:: It seems I forgot to mention that I'm trying to get from a specific vertex to another specific vertex. Quite important point there :/

EDIT2:: As someone below pointed out, I should highlight that edge weights are non negative.

Virilism

So is it maximum minimum or minimum maximum? Please edit the example and correct. – Dictograph

@Jasiu: Both the title and example say "maximum minimum weight" (i.e. a path whose minimum weight is as large as possible). What's to correct? – Lefton

Am I correct in thinking that you only are interested in paths having minimum edge count across all paths? I.e. if there exists a path with weights (2, 2, 2), you're not interested in the path (5, 6, 7, 8), right? – Sectarianize

@j_random_hacker: No, (2,2,2) has minimum weight 2 and (5,6,7,8) has minimum weight 5, so the latter is better. – Lefton

Answer 1

Use either Prim's or Kruskal's algorithm. Just modify them so they stop when they find out that the vertices you ask about are connected.

EDIT: You ask for maximum minimum, but your example looks like you want minimum maximum. In case of maximum minimum Kruskal's algorithm won't work.

EDIT: The example is okay, my mistake. Only Prim's algorithm will work then.

Dictograph

Ah, starting with the edges ordered in descending order of weight? This is a great idea, and it's easy to prove it works. :) – Lefton

I definitely want maximum minimum. As my example shows: Minimum of (10,1,10) = 1 Minimum of (2,2,2) = 2 Maximum = 2 – Virilism

Yes, I must have read something wrong :). So Prim's algorithm is the one that stays in the game. – Dictograph

I know I didn't put it down as a requirement, but presumably prims will not always return the shortest Maximin path (shortest as in least edges traversed)? Obviously I'm simulating some sort of pipe network and if I don't use the shortest path then capacity gets wasted. I'm not too worried about that at the moment to be honest, but if I'm wrong and prims will return the shorest maximin path that's excellent :) – Virilism

Kruskal's will also work. (Start with edges sorted in descending order of weight, add one by one till the two vertices are in the same component.) – Lefton

Martin, you can do it in two phases: First, compute the maximum minimum path. Then you'll have the weight of the edge. Now you can run BFS or Dijkstra in order to find the shortest path, shortest meaning least edges (use BFS then) or lowest total weight (use Dijkstra then). Modify these algorithms so they don't take into account edges lighter then the value computed in the first part. – Dictograph

I'm not convinced that either Prim's or Kruskal's algorithm will work here. Would someone mind updating the answer with a more detailed proof? Thanks! – Sectarianize

@Sectarianize I have added a proof of correctness of the algorithm here #18553464 – Robers

It seems that nobody noticed that "maximum minimum" and "minimum maximum" are equivalent: Just change the signs of the weights – Microeconomics

Answer 2

I am copying this answer and adding also adding my proof of correctness for the algorithm:

I would use some variant of Dijkstra's. I took the pseudo code below directly from Wikipedia and only changed 5 small things:

1. Renamed dist to width (from line 3 on)
2. Initialized each width to -infinity (line 3)
3. Initialized the width of the source to infinity (line 8)
4. Set the finish criterion to -infinity (line 14)
5. Modified the update function and sign (line 20 + 21)

1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                 // Initializations
3          width[v] := -infinity  ;                                // Unknown width function from 
4                                                                  // source to v
5          previous[v] := undefined ;                              // Previous node in optimal path
6      end for                                                     // from source
7      
8      width[source] := infinity ;                                 // Width from source to source
9      Q := the set of all nodes in Graph ;                        // All nodes in the graph are
10                                                                 // unoptimized – thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with largest width in width[] ;       // Source node in first case
13          remove u from Q ;
14          if width[u] = -infinity:
15              break ;                                            // all remaining vertices are
16          end if                                                 // inaccessible from source
17          
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                 // removed from Q.
20              alt := max(width[v], min(width[u], width_between(u, v))) ;
21              if alt > width[v]:                                 // Relax (u,v,a)
22                  width[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25              end if
26          end for
27      end while
28      return width;
29  endfunction

Some (handwaving) explanation why this works: you start with the source. From there, you have infinite capacity to itself. Now you check all neighbors of the source. Assume the edges don't all have the same capacity (in your example, say (s, a) = 300). Then, there is no better way to reach b then via (s, b), so you know the best case capacity of b. You continue going to the best neighbors of the known set of vertices, until you reach all vertices.

Proof of correctness of algorithm:

At any point in the algorithm, there will be 2 sets of vertices A and B. The vertices in A will be the vertices to which the correct maximum minimum capacity path has been found. And set B has vertices to which we haven't found the answer.

Inductive Hypothesis: At any step, all vertices in set A have the correct values of maximum minimum capacity path to them. ie., all previous iterations are correct.

Correctness of base case: When the set A has the vertex S only. Then the value to S is infinity, which is correct.

In current iteration, we set

val[W] = max(val[W], min(val[V], width_between(V-W)))

Inductive step: Suppose, W is the vertex in set B with the largest val[W]. And W is dequeued from the queue and W has been set the answer val[W].

Now, we need to show that every other S-W path has a width <= val[W]. This will be always true because all other ways of reaching W will go through some other vertex (call it X) in the set B.

And for all other vertices X in set B, val[X] <= val[W]

Thus any other path to W will be constrained by val[X], which is never greater than val[W].

Thus the current estimate of val[W] is optimum and hence algorithm computes the correct values for all the vertices.

Robers

what's the meaning of the line 24 "decrease key v in Q" – Gorden

and what if there are two same largest width in the Q, we would choose the certain one or arbitrary one – Gorden

Answer 3

You could also use the "binary search on the answer" paradigm. That is, do a binary search on the weights, testing for each weight w whether you can find a path in the graph using only edges of weight greater than w.

The largest w for which you can (found through binary search) gives the answer. Note that you only need to check if a path exists, so just an O(|E|) breadth-first/depth-first search, not a shortest-path. So it's O(|E|*log(max W)) in all, comparable to the Dijkstra/Kruskal/Prim's O(|E|log |V|) (and I can't immediately see a proof of those, too).

Lefton

That's an interesting technique, and it certainly sounds like it should work. – Virilism

@ShreevatsaR, your approach of binary searching the answer can be optimized to run in linear time. see here en.wikipedia.org/wiki/Widest_path_problem#Undirected_graphs And I have added a proof of the correctness of the algorithm here #18553464 – Robers

@NikunjBanka: Thanks. But why did someone downvote this answer? – Lefton

Dont know. I am upvoting it. And frankly speaking I cant understand how can we implement your approach in linear time. If you understand it, please consider adding it in your answer. – Robers

@NikunjBanka: I understand the linear time algorithm mentioned on the Wikipedia page you linked to. It rests on the linear-time median-finding algorithm. (1) Take all the |E| edges and find their median weight (say M) in linear (O(|E|)) time. (2) As above, check reachability in the graph, using only edges of weight greater than this median M. If a path was found, then (3a) we now know for sure we don't need any edge of weight less than M. Drop all of them, and go back to step 1. Else, (3b) contract edges (u,v) of weight greater than M (collapse (u,v) to single vertex) and go back to step 1. – Lefton

@NikunjBanka: When you contract an edge (u,v), for every other vertex w adjacent to either u or v in the original graph, you add an edge from w to the new vertex. The weight of this edge is: if w was incident to only one of the two, then the weight of that edge, else the larger of the two weights. See zib.de/Publications/Reports/ZR-06-22.pdf for details. – Lefton

The edge contraction you explained is more complex than I expected. Also would you mind having a look at this question #22876299 . It is very similar and I think it should also be solved by binary searching the answer. – Robers

Answer 4

I am not sure that Prim will work here. Take this counterexample:

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 4), (4, 2)}

weight function w:
  w((1,2)) = .1, 
  w((2,3)) = .3
  w((1,4)) = .2
  w((4,2)) = .25

If you apply Prim to find the maxmin path from 1 to 3, starting from 1 will select the 1 --> 2 --> 3 path, while the max-min distance is attained for the path that goes through 4.

Polard

Answer 5

This can be solved using a BFS style algorithm, however you need two variations:

• Instead of marking each node as "visited", you mark it with the minimum weight along the path you took to reach it.

For example, if I and J are neighbors, I has value w1, and the weight of the edge between them is w2, then J=min(w1, w2).

• If you reach a marked node with value w1, you might need to remark and process it again, if assigning a new value w2 (and w2>w1). This is required to make sure you get the maximum of all minimums.

For example, if I and J are neighbors, I has value w1, J has value w2, and the weight of the edge between them is w3, then if min(w2, w3) > w1 you must remark J and process all it's neighbors again.

Vardon

Why would this terminate in polynomial time? (It looks correct, but doesn't look polynomial-time.) – Lefton

I imagine that the worst case for this algorithm would be pretty nasty. I can't see any problems with the algorithm except that the "process all it's neighbours again" is a bit fuzzy, wouldn't you have to process the entire path back to the source again? – Virilism

Answer 6

Ok, answering my own question here just to try and get a bit of feedback I had on the tentative solution I worked out before posting here:

Each node stores a "path fragment", this is the entire path to itself so far.

0) set current vertex to the starting vertex
1) Generate all path fragments from this vertex and add them to a priority queue
2) Take the fragment off the top off the priority queue, and set the current vertex to the ending vertex of that path
3) If the current vertex is the target vertex, then return the path
4) goto 1

I'm not sure this will find the best path though, I think the exit condition in step three is a little ambitious. I can't think of a better exit condition though, since this algorithm doesn't close vertices (a vertex can be referenced in as many path fragments as it likes) you can't just wait until all vertices are closed (like Dijkstra's for example)

Virilism

Good work...this is just Prim's algorithm as suggested by Jasiu. ;) – Bijouterie

Wonderful, I do love it when I reinvent the wheel >_< Well I guess I have a fairly good understanding of how his suggestion works then ;) – Virilism

Answer 7

You can still use Dijkstra's!

Instead of using +, use the min() operator.
In addition, you'll want to orient the heap/priority_queue so that the biggest things are on top.

Something like this should work: (i've probably missed some implementation details)

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
   current = pq.top()
   pq.pop()
   for all neighbors of current.node:
      if neighbor has not been visited
          pq.decrease_key(neighbor, min(current.weight, edge.weight))

It is guaranteed that whenever you get to a node you followed an optimal path (since you find all possibilities in decreasing order, and you can never improve your path by adding an edge)

The time bounds are the same as Dijkstra's - O(Vlog(E)).

EDIT: oh wait, this is basically what you posted. LOL.

Morula

No, Dijkstra's doesn't work here, for reasons similar to why it doesn't work on graphs with negative edge weight. – Rental

(for a counterexample, see my posting) – Rental