0

给定一个网络流 G(V,E)。在我们运行 FF 算法并得到一个残差 grpah Gf 和一个 min-cut (S,T)

我想知道边 E′⊂ E 的最小数量，这样每个 e ∈ E 的容量增加一个单位将使最大流量增加到 val(f)+1。该算法应该在 O(E*log(V)) 中运行。

这是我的方法。

对于每个交叉边 (u,v)

(1) 使用 BFS 找到 u 的部分增广路径 s；以及从 v 到 t 的所有部分增广路径。如果两个这样的部分增广路径都存在。然后增加（u，v）可以使最大流量增加一。

如果 (1) 为假，

可能性很小

(a) 在残差中，源 s 没有出边

(b) 在残差中，sink t 没有传入边。

(c) 以上两种情况都发生

在 (a) 的情况下，最小切割有一组仅包含源 s。找到从交叉边缘到 t 的最短路径，这个距离 + 1（交叉边缘）将是我们的最小值。通过在 O(E*log(V)) 时间内使用 Dijlstra 算法

在 (b) 的情况下，类似地，找到从交叉边缘到 t 的最短路径（假设这个交叉边缘是 (u,v) 和 T 中的 v，v 到 t 是所有交叉边缘的最短路径），这距离 + 1 + 从 s 到 u 的最短路径的距离 = 将所有容量增加 1 的最小边数，导致最大流量增加 1

在 (c) 的情况下，我们需要寻找从 s 到 t 的最短路径；我们可以在 O(E*log(V)) 时间内应用 Dijlstra 算法。

但是，我认为上述方法可以达到目标但效率不高（特别是在处理情况（2）时，它可能无法在 E*log(V) 时间内运行）。

有没有更容易接近的方法？

4

1 回答 1

0

如果容量是整数，那么这似乎相当简单。

从 S 开始，使用深度优先搜索来查找使用具有备用容量的链接从那里可到达的所有节点。将这些节点放在一个集合中并标记它们。

从 T 使用深度优先搜索来找到所有可以使用具有备用容量的链接到达 T 的节点。以不同的方式标记这些节点。

使用广度优先搜索找到从 S 可达的任何节点到可以到达 T 的任何节点的最短路径。从 S 可达的节点集开始。在每个阶段查看是否有任何可以到达 T 的节点是当前集合中的一个节点。如果是这样，那么你就完成了。如果不是，则下一阶段的集合是当前集合中未标记的节点的邻居集合。标记新集中的所有节点。

如果容量不是整数，那么创建任何流都不会给你至少一个容量流，那么我认为你在https://en.wikipedia.org/wiki/Minimum-cost_flow_problem的土地上。

于 2017-12-10T05:53:46.483 回答