algorithm - 为什么在 Ford-Fulkerson 算法中需要后边？

Question

为了在图中找到最大流量，为什么不考虑后边仅使该路径中具有最小边容量的所有增广路径饱和就不够了？我的意思是，如果我们假设从它流出，称它为后边缘有什么意义？

Answer 1

在执行 Ford-Fulkerson 算法时，后边缘是必要的，以防您选择的路径最终不是整个流程的一部分。

作为需要后边缘的示例，请考虑以下流网络：

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

假设所有边都指向下方并且所有边的容量为 1，并且您想要找到从 s 到 t 的流。假设在 Ford-Fulkerson 的第一次迭代中，您采用路径 s → b → c → t。此时，您已将一个单位的流量从 s 推到 t。如果您不添加任何后边缘，则剩下以下内容：

    s
   / 
  a   b
   \   \
    c   d
       /
      t

没有更多的 st 路径，但这并不意味着您有最大流量。您可以通过发送一个沿路径 s → a → c → t 和另一个沿路径 s → b → d → t 将两个流单元从 s 推到 t。如果剩余流网络中没有任何后边缘，您将永远不会发现这条其他路径。

希望这可以帮助！