在图中查找具有最大最小容量的路径

Question

我正在帮助一个与工作相关的项目的朋友,他需要计算从节点a到节点b的最大容量,其中边缘具有容量.然而,从a到b的路径中的最大容量受到具有最低容量的边缘的限制.

让我试着用一个简单的样本来解释

因此,图是带有加权边的有向图,它可以是循环的.容量最大的路径为s-> b-> t,容量为250,因为该边缘设置了限制.

我做了一些阅读,发现这类问题是"最广泛的路径问题",或者我称之为最小容量最大的路径,但我没有找到任何示例或任何伪代码解释如何解决这个问题.

我正在考虑使用BFS找到从s到t的所有路径,并且某种方式只允许在路径中访问一个节点,然后在路径中找到最小值,这是否有效？

Answer 1

我会使用Dijkstra的一些变体.我直接从维基百科中获取了下面的伪代码,只改变了5件小事:

1. 改名dist为width(从第3行开始)
2. 初始化width为-infinity(第3行)
3. 将源的宽度初始化为infinity(第8行)
4. 将完成标准设置为-infinity(第14行)
5. 修改了更新功能和签名(第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

一些(handwaving)解释为什么这样做:你从源头开始.从那里,你拥有无限的能力.现在检查源的所有邻居.假设边缘并不都具有相同的容量(例如,在您的示例中(s, a) = 300).然后,没有更好的方法来b通过(s, b),所以你知道最好的情况容量b.您继续前往已知顶点集的最佳邻居,直到到达所有顶点.

Answer 2

上面的答案得到了很好的解释.万一有人需要解释算法的正确性,请转到:

证明:

在算法的任何点,将有2台的顶点A和B的.A中的顶点将是找到正确的最大最小容量路径的顶点.并且集合B具有我们尚未找到答案的顶点.

归纳假设:在任何步骤中,集合A中的所有顶点都具有到它们的最大最小容量路径的正确值.即,所有先前的迭代都是正确的.

基本情况的正确性:当集合A仅具有顶点S时.那么S的值是无穷大,这是正确的.

在当前的迭代中,我们设置

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

归纳步骤:假设,W是集合B中具有最大val [W]的顶点.并且W从队列中出队,W已经设置了答案值[W].

现在,我们需要显示每个其他SW路径的宽度<= val [W].这将永远是正确的,因为到达W的所有其他方式将通过集合B中的某些其他顶点(称为X).

对于集合B中的所有其他顶点X,val [X] <= val [W]

因此,到W的任何其他路径将受到val [X]的约束,其永远不会大于val [W].

因此,val [W]的当前估计是最佳的,因此算法计算所有顶点的正确值.