Ford Fulkerson 算法增加流量

Question

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

我遇到的问题是，我不知道如何获得解决方案中的值。
有人可以解释一下吗？

Answer 1

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

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

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

在你的例子中，我们可以

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

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