如何构造计算最大流的Dinic算法的水平图？

Question

我正在阅读迪尼奇算法来解决最大流问题，该算法对给定源S和接收器T的图G说明如下：

1. 将每个边的流设置为0。
2. 从Gf构造级别图GL (其中Gf是残差图)
3. 在GL中查找阻塞流
4. 添加增强流，然后返回到2

在网上进行了一些研究之后，我了解了GL是如何计算的，前提是T位于最后一个水平，或者T是离S最远的跳数。

但是，我不明白当点离S比T离S更远时，是如何做到这一点的。

例如，在下面的图像中，我理解如何为图1中显示的残差图Gf构造GL，但是我不确定如何为图2中显示的残差图GL绘制级别图GL。

有人能帮我理解一下是怎么做到的吗？

图片：

​

​

Answer 1

要计算水平图，在每一步，您必须采取所有的顶点没有任何前身，然后删除这些顶点为下一步。因此，在第二个示例中，您有以下内容：

• 步骤0: s位于0级(剩余图是由顶点A、B、C、D、E、F、T诱导的图)
• 步骤1: A和B位于1级(剩余图是由顶点C、D、E、F、T诱导的图)
• 步骤2: C和D位于2级(剩余图是由顶点E、F、T诱导的图)
• 步骤3: e位于第3级(剩余图是由顶点F和T诱导的图)
• 步骤4: F位于第4级(剩余图为单节点T)
• 步骤5: t在5级

你不能在第三步取T，因为从F到T还有一个弧线。