重标签到前端算法

Relabel-to-front 算法用于确定网络的は最大流。与 generic push-relabel 方法相比，relabel-to-front 算法效率更高。在使用 push-relabel 方法时，push 和 relabel 的基本操作可以按任意顺序进行。relabel-to-front 算法则精心选择顺序并有效地控制网络数据结构。

首先，我们必须理解基本操作，例如 push 和 relabel。

每个顶点都连接着 height (h) 变量和 excess flow (e) 变量。

• Push (推送)：当一个顶点有过剩的流，并且在剩余图中相邻的节点高度较低时，我们将流从该顶点推送到高度较低的节点。
• Relabel (重标记)：当一个顶点过多的流，并且附近没有较低高度的节点时，我们使用 relabel 操作来提高该顶点的高度，以便它可以执行 push 操作。

relabel-to-front 算法在一个列表中跟踪网络的顶点。它从列表的开头开始，重复选择一个过剩的顶点 u 并对其执行 discharge 操作。

在 discharge 操作期间执行 push 和 relabel 操作，直到顶点 u 没有正过剩流 (e)。

如果一个顶点被重标记，算法将从列表的开头再次扫描，并将新顶点放在列表的最前面。

算法

• 为上述 generic push-relabel 算法设置 preflow 和 height 的初始值。
• 从头开始创建列表 L，排除源和汇。
• 将每个顶点的当前指针设置为其邻居列表 N 中的第一个顶点。在邻居列表 N 中包含存在剩余边的那些顶点。
• 当算法到达列表 L 的末尾时。
• 选择列表 L 中的顶点 u 并对其执行 discharge 操作。
• 如果顶点 u 由于 discharge 操作而被重标记，则将其移到列表的顶部。
• 如果顶点 u 被移到列表的顶部，则下一迭代中的顶点是它在列表中的新位置之后的那个顶点。

示例

• 以流网络为例。右侧显示了初始列表 L=(B, C)，初始值为 u=B。
  
• 在 preflow 初始化之后。在列表 L 中的每个顶点下方都有一个邻居列表 N，其中当前邻居被圈出。
  
• 由于顶点 B 具有 3 的过剩流 (e=3)，因此执行 discharge 操作。顶点 B 执行 relabel 操作 (h=1)，并将流 1 推送到顶点 C，因为它没有高度更低的节点。
  
• 顶点 B 执行 relabel 操作 (h=5)，并将流 2 推送到顶点 A，因为它仍然有 2 的过剩流 (e=2)。尽管顶点 B 的标签已更改，但它仍然位于列表的顶部。现在顶点 C 有 1 的过剩流 (e=1)，它被 discharge。
  
• 顶点 C 执行 relabel 操作 (h=1)，并将流 1 推送到节点 D。由于顶点 C 执行了 relabel 操作，因此将其移到列表的顶部。
  
• 现在，在 L 中，顶点 C 后面是顶点 B，但 B 没有过剩流。当它到达列表 L 的末尾时，RELABEL-TO-FRONT 结束。由于没有过剩的顶点，preflow 达到最大值。此时，最大流为 1。
• 时间复杂度：在网络 G (V, E) 上运行时间为 O(V3)。因此，它比 generic push-relabel 算法 (其完成时间为 O(V2E)) 具有更好的性能。