为什么Ford-Fulkerson算法需要后沿？

Question

为了找到图中的最大流量,为什么不仅仅考虑该路径中具有最小边缘容量的所有增强路径而不考虑后边缘就足够了？我的意思是,如果我们从它那里假设流量,那么称它为后沿是什么意思呢？

Answer 1

在执行Ford-Fulkerson算法时,如果您选择的路径最终不是整个流程的一部分,则需要后沿.

作为需要后沿的示例,请考虑此流网络:

    s
   / \
  a   b
   \ / \
    c   d
     \ /
      t

假设所有边都指向下方并且所有边都具有容量1并且您想要找到从s到t的流.假设在Ford-Fulkerson的第一次迭代中你采用了路径s - > b - > c - > t.此时,您已将一个流量单位从s推到t.如果你没有添加任何后边缘,你就会留下这个:

没有更多的st路径,但这并不意味着你有最大流量.您可以通过沿路径s - > a - > c - > t发送一个流量从s到t来推动两个流量单位,另一个沿路径s - > b - > d - > t.在残余流网络中没有任何后边缘,您将永远不会发现这条其他路径.

希望这可以帮助!

我有一个基本问题，如果上图是有向的，在添加回 ekdge 后..第二个流量将是容量 1 的 s->a->c -> b -> d ->t，因此最大流量为 2 ，其中很好...但是如果与现实生活中连接管道的示例相比，c->b 之间没有管道，那么它是如何工作的呢？ (2认同)
令人惊讶的是，一个简单的例子可以阐明整个算法。 (2认同)