11

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

让我试着用一个简单的例子来解释 简单示例图

所以该图是一个带加权边的有向图，它可以是循环的。具有最高容量的路径将是 s->b->t 并且容量为 250，因为该边设置了限制。

我做了一些阅读，发现这种类型的问题是“最宽路径问题”，或者我将其称为具有最大最小容量的路径，但我没有找到任何示例或任何伪代码来解释如何来解决这个问题。

我正在考虑查找从 s 到 t 的所有路径，使用 BFS 并且以某种方式只允许在路径中访问一次节点，然后找到路径中的最小值，这行得通吗？

4

2 回答 2

14

我会使用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

一些（挥手）解释为什么这样做：你从源头开始。从那里，你对自己拥有无限的能力。现在您检查源的所有邻居。假设边缘并不都具有相同的容量（在您的示例中，例如(s, a) = 300）。那么，没有比bvia更好的到达方式了(s, b)，所以你知道 的最佳案例容量b。您继续前往已知顶点集的最佳邻居，直到到达所有顶点。

于 2013-08-31T22:02:36.570 回答
12

上面的答案已经很好地解释了。以防万一有人需要解释算法的正确性，请看：

证明：

在算法中的任何一点，都会有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 已被设置为答案 val[W]。

现在，我们需要证明每个其他 SW 路径的宽度 <= val[W]。这总是正确的，因为到达 W 的所有其他方式都将通过集合 B 中的某个其他顶点（称为 X）。

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

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

因此，当前对 val[W] 的估计是最优的，因此算法计算所有顶点的正确值。

于 2014-04-06T05:01:57.940 回答