Finding path with maximum minimum capacity in graph

Question

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?

Answer 1

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.