我正在阅读 Dinic's Algorithm解决最大流问题,对于给定源 S 和汇 T 的图 G,算法说明如下:
- 设置每条边的流量为0
- 从Gf构造层级图GL(其中Gf是残差图)
- 在 GL 中找到阻塞流
- 添加增广流并回到2
经过一些在线研究后,我了解了如何计算 GL,前提是 T 位于最后一层,或者 T 是距 S 最远的跳数。
但是我不明白当顶点离 S 比 T 离 S 更远时,这是如何完成的。
例如在下图中,我了解如何为图 1 中所示的残差图 Gf 构建 GL,但是我不确定如何为图 2 中所示的残差图绘制水平图 GL。
如何做到这一点?
图片:
最佳答案
要计算层级图,在每一步中,您必须获取所有没有任何前驱的顶点,然后在下一步中删除这些顶点。 在你的第二个例子中,你有以下内容:
- 第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还有一条弧。
关于algorithm - 如何为计算最大流量的 Dinic 算法构建级别图?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48746680/