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

没有更多的 s-t 路径，但这并不意味着您拥有最大流量。您可以将两个单位的流量从 s 推到 t，方法是将一个单位沿着路径 s → a → c → t 发送，另一个沿着路径 s → b → d → t。如果残差流网络中没有任何后向边缘，您将永远不会发现这条其他路径。

希望这对您有所帮助!