Finding path with maximum minimum capacity in grap

问题:

I am helping a friend with a work related project where, he needs to calculate the maximum capacity from a node a to a node b, where the edge has a capacity. However the maximum capacity in a path from a to b is limited by the edge with the lowest capacity.

Let me try to explain with a simple sample

So the graph is a directed graph with weighted edges, and it can be cyclic. The path with the highest capacity would be s->b->t and have the capacity of 250, since that edge is setting the limit.

I have done a bit of reading and found out that this type of problem is a "Widest path problem" or I would call it something like a path with maximum minimum capacity, but I haven't found any examples or any pseudo code explaining how to tackle this.

I was thinking something in the lines of finding all paths from s to t, using BFS and somehow only to allow visiting a node once in a path, and then find the minimum value in the path, would that work?

回答1:

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.

回答2:

The above answer has been very well explained. Just in case anyone needs an explanation of the correctness of the algorithm, here you go:

Proof:

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.