algorithm - Ford Fulkerson 算法增加流量

Question

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

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

标签： algorithmgraph-theoryford-fulkerson

Answer 1

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

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

看起来您的示例包含一个子图，因为顶点 X、Y 和 Z 违反了流量守恒（每个顶点的传入流量之和应为零）。

在您的示例中，我们可以

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

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