Finding the path with the maximum minimum capacity in the graph

Question

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

Let me try to explain a simple example.

Thus, the graph is a directed graph with weighted edges and can be cyclic. The path with the largest capacity will be s-> b-> t and have a capacity of 250, since this edge sets the limit.

I did a bit of work and found out that this type of problem is a “Widest path problem” or I would call it something like a path with a maximum minimum capacity, but I did not find any examples or pseudo-codes explaining how to handle this.

I thought something in the search strings of all paths from s to t, using BFS and somehow just to allow the node to visit once in the path and then find the minimum value in the path, will this work?

Answer 1

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

• Renamed dist to width (from line 3)
• Initialize each width to -infinity (line 3)
• Initialize the width of the source to infinity (line 8)
• Set the termination criterion to -infinity (line 14)
• Updated 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 (manual) explanation of why this works: you start from the source. From there you have an infinite capacity for yourself. Now you check all source neighbors. Suppose the ribs do not have the same capacity (in your example, say (s, a) = 300 ). Then there is no better way to reach b , then through (s, b) , so that you know the maximum capacity of b . You continue to walk to the best neighbors of a known set of peaks until you reach all the peaks.

Answer 2

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

Evidence:

At any point in the algorithm there will be 2 sets of vertices A and B. The vertices in will be the vertices for which the correct path of maximum minimum capacity is found. And the set B has peaks for which we did not find the answer.

Inductive hypothesis . At each step, all the vertices in the set A have the correct path values ​​of the maximum minimum capacity for them. those. all previous iterations are correct.

The correctness of the base case : when the set A has only the vertex S. Then the value of S is equal to infinity, which is true.

In the current iteration, we set

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

Inductive step . Suppose that W is a vertex in the set B with the largest val [W]. And W was put out of the queue from the queue, and W the answer val [W] was set.

Now we need to show that every other SW path has a width of & lt; = val [W]. This will always be true, because all other ways to reach W will go through some other vertex (let's call it X) in B.

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

Thus, any other path to W will be limited to val [X], which will never be more than val [W].

Thus, the current val [W] estimate is optimal and, therefore, the algorithm calculates the correct values ​​for all vertices.