push flow relabel algorithm

Question

V wrt中顶点的有效标记。一个预流x是一个函数d：N - >满足Z：[。]

d [秒] = N^d [T] = 0

所有（V，W）属于E：d [v] < = d [W] + 1

假设我们有4个verticies包括（s和t）

那么我们有d [秒] =根据我们应具有有效标记4

d [v] < = d [w] +1，但对于来自's'的边缘，它不是 有效因为使用4 < = 1是错误的。这个逻辑不仅是源头吗？

我是否认为它正确？请纠正我。

感谢您的时间和帮助

Answer 1

你有效的标签定义是接近，但不完全正确。

你声称d [V] < = d [W] + 1所有（V，W）属于E.

然而，这实际上只需要为所有真（V，W）属于R，其中R是残差边缘。

残余边缘是电流小于边缘容量的边缘。

在topcoder有一个很好的解释。

考虑这个图：

在上边缘（如2/3）标签的第一个数字给出了电流流过，而第二个数字给出了边缘的能力。

节点上的数字给出每个节点的高度函数d。

绿色的边缘是剩余边缘，因为它们有空闲的容量。

所以要检查高度约束，我们只需要检查S-> A边和B-> T边。