algorithm - 如何为计算最大流量的 Dinic 算法构建级别图？

Question

我正在阅读 Dinic's Algorithm解决最大流问题，对于给定源 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。

如何做到这一点？

图片:

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 级

你不能在第3步取T，因为从F到T还有一条弧。