algorithm - 饱和推送的最大流量通用推送重标记算法时间复杂度

Question

我在这里检查了算法介绍第三版第747页（http://kddlab.zjgsu.edu.cn:7200/students/lipengcheng/%E7%AE%97%E6%B3%95%E5%AF%BC% E8%AE%BA%EF%BC%88%E8%8B%B1%E6%96%87%E7%AC%AC%E4%B8%89%E7%89%88%EF%BC%89.pdf）

根据推论 26.25，饱和推送操作可以在 O(1) 中完成。但是如何实现 O(1) 呢？

我认为至少我需要 O(V) 来搜索 (u, v) 可能到 Push(u, v)。O(1)中的运算可以使用什么数据结构？

标签： algorithmdata-structuresgraphmax-flow

Answer 1

如第739 页所述，推送操作本身显然在O (1) 中有效，因为它不包含循环。此外，正如推论 26.25 所声称的，我们需要一种O (1) 方式来找到要执行的适用操作（推送或重新标记）。这将在下一节中实现，即 relabel-to-front 算法。请参阅第 755 页上的relabel-to-front伪代码和第 751 页上的放电伪代码。