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

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.