algorithm - Ford Fulkerson 算法增加流量

Question

关于 Ford Fulkerson使用路径 s-x-y-z-t 的算法，我们必须找出如何增加沿该路径的流量。

我遇到的问题是，我不知道如何获取解决方案中的值。
谁能解释一下？

Answer 1

为了在 Ford-Fulkerson 算法中找到增广路径，我们需要查看 residual graph , 这基本上允许我们

• 继续在非饱和边缘添加流量或
• 从边缘移除现有流。

看起来您的示例由一个子图组成，因为顶点 X、Y 和 Z 违反了流量守恒(每个顶点的流入流量之和应为零)。

在你的例子中，我们可以

• 沿 SX 边再推 7 个；
• 沿 XY 边再推 4 个；
• 从 YZ 边缘移除 3 个单位；
• 沿着 ZT 边再推 4 个单元。

因此，在不违反任何容量限制的情况下，我们最多可以将 3 个单元从 S 推到 T。通过这样做，我们最终得到了第二张图片中描述的流量网络。