algorithm - Ford Fulkerson.. 向后边缘的目的是什么？

Question

我正在学习 Ford Fulkerson 算法，但我对向后边缘的用途以及它们如何帮助我们达到最大流量感到困惑。我已经观看了几个不同的视频并阅读了一些关于该算法的文档，但没有任何点击。也许这里有人可以用一种对我有意义的方式来表达它!

Answer 1

Gassa 的评论是正确的。这是一个简单的例子。

假设您有源 S、汇 T 和两个中间节点 A 和 B，以及从 S 到 A 和 A 到 T，以及从 S 到 B 和 B 到 T 的容量为 1 的路径。

  A
 / \
S   T
 \ /
  B

显然，每条边都有一个权重为 2 的流。现在，添加一条从 A 到 B 的边，容量为 1。

  A
 /|\
S V T
 \|/
  B

这不会增加最大流量，但它会让您有机会在增量创建流量时搞砸。你可以从 S->A->B->T 开始。

  A
 /|
S V T
  |/
  B

为了找到最大流量，您需要能够减少从 A 到 B 的流量。您可以通过沿着 S->B->A->T 增加流量来实现。

  A         A         A
 /|         |\       / \
S V T  +  S ^ T  =  S   T
  |/       \|        \ /
  B         B         B

沿 A->B 向后移动意味着您减少从 A 到 B 的流量。