0

我对 Ford-Fulkerson 算法的分析不正确。例如，请看下图：

      _____>4___>_
     |            |
0--->1---->3------6
|    |            | 
2--->5--------->---

节点 0 是源节点，节点 6 是终端节点，每条边的限制都是 1，除了节点 0 到 1 的边的限制是 2。如果流从 0->1->3->6 和 0- >1->4->6 和 0->2->5->6，图形的流向是 3。但是，如果流从 0->1 开始，则选择从 0->1->3 开始->6 和 0->1->5->6，我们不能再从 0->2->5->6 走，因为 5->6 已经被占用了。由于 0->1 的限制是 2，所以我们只能从 0->1 开始两次，因此，图的流量是 2。显然，图的最大可能流量应该是 3 而不是 2。请问 Ford-Fulkerson算法处理这个问题并总是返回 3 作为答案？

4

2 回答 2

1

是的，福特-富尔克森可以。始终解决此类问题实际上是它的设计目的。

我想您缺少的事实是，在确定残差图时，您还必须添加后边缘。因此，经过 0->1->3->6 和 0->1->5->6 之后，残差图实际上如下所示：

                1          1
            +-------> 4 ------+
            |                 |
        2   |     1        1  v
  0 <------ 1 <----- 3 <----- 6
  |         ^                 |
  |   1     | 1               | 1
  +-------> 5 <---------------+

Ford-Fulkerson 将采取的下一步是添加路线 0->5->1->4->6，从而产生 3 的流。

于 2013-03-04T21:46:52.183 回答
0

当 maxFlow 太高时它会超时。（在最坏的情况下，福特 fulkerson 在每一步仅添加 1 个流）

只需在 Ford fulkerson 中使用 BFS 而不是 DFS，它就会变成Edmonds 鲤鱼！与福特-富尔克森相比，它的速度太快且使用广泛。

您还可以查看此处解释的 PFS（优先搜索）。

于 2014-06-30T21:54:35.057 回答