algorithm - Ford-Fulkerson 似乎不适用于此图表

Question

我对 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 作为答案？

Answer 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。