福特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.通过这样做，我们最终得到了第二张图片中描述的流网络。