algorithm - 在最大流量算法中计算过量流量和溢出

Question

我正在以下链接阅读推流算法。

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel

提到了多余流量 - 我们将多余流量 e 定义为 e(u) = f(V,u)，即流入 u 的净流量。如果 e(u) > 0，则顶点 u ∊ V-{s,t} 溢出/激活。

我正在寻找简单流网络的示例，我们如何计算 e(u) ？

感谢您的时间和帮助。

Answer 1

在下图中，有一个源节点 (S)、一个汇节点 (T) 和一个内部节点 (A)。

这些数字给出了流量（比如每秒升数）。每秒有 3 升水进入 A，但每秒只有 1 升离开 A，所以 A 的多余流量为 2。

笔记

1. 在 push-relabel 算法中，内部节点的多余流量不能是负数。换句话说，您不允许离开的流量多于进入的流量。

2. 允许源节点产生流（不计入内部节点，所以注1不适用）

3. 在算法过程中，多余的流量被减少，直到最后所有的顶点都有 0 多余的流量

4. 您可以通过将所有流入流量相加并减去所有流出流量来计算过剩流量。

5. 但是，在实践中，该算法会维护一组多余的流量，并随着算法的进行更新值。