algorithm - 如何将具有过剩流量的预流推送网络转换为流量网络

Question

我为最大流实现了最高标签推送重新标记算法的第一阶段，但我找不到任何关于如何实现第二阶段的资源，即将预流推送网络转换为有效流网络。

Answer 1

如果您真的需要最大流(可以直接从预流中导出最小切割并使用它来验证预流)，那么我知道两种方法。

第一种方法在关于推送重新标记算法的原始 Goldberg-Tarjan 论文中有所介绍。从本质上讲，第二阶段的实现几乎与第一阶段完全相同。唯一的区别是源保持在距离 n 处(而不是汇点，距离为 0)。这具有将多余的路由回源头的效果。

我不确定在哪里描述了第二种方法。我知道这是在 Goldberg 的实现中，Boost Graph implementation基于(参见 convert_preflow_to_flow)。从概念上讲，分为三个步骤。

1. 直到预流是非循环的，通过在反向循环上发送足够的流以从流图中删除一条弧来取消流循环。

2. 按照从最下沉到最源的顺序对流图的节点进行拓扑排序。

3. 对于拓扑顺序中的每个节点，通过减少传入弧上的流量来消除其多余部分(这会相应增加尚未处理的多余节点)。

实际上，第 1 步和第 2 步都涉及深度优先搜索。天真地，人们会在检测到并取消每个循环后重新开始深度优先搜索以进行循环检测，但是可以将深度优先搜索倒回到它第一次使用取消删除的弧的位置，从而节省时间再次在搜索中达到这一点。拓扑顺序可以作为搜索的副产品获得，从而节省了步骤 2 的单独遍历。