計算過流和最大流量算法

Question

四溢，我在下面的鏈接閱讀推流算法。

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

要提及的是 用過流量 - 我們定義過量水流E爲e（U）= F（V，U），所述氣流成網Ú。甲頂點uεN- {S，T}的溢出/活性如果E（u）的> 0

我尋找例如用簡單流網絡我們如何計算E（u）的？

感謝您的時間和幫助。

Answer 1

在該圖中下面有一個源節點（S），宿節點（T），和一個內部節點（A）。

的數字給出（每秒發言權升）的流量。有每秒進入一個3升，但每秒離去，一個只1升這樣的過量流動對A爲2

注

1. 在推重新標籤算法，過量流爲內部節點不能是負面的。換句話說，你不允許有更多的流量進入。

2. 被允許生成流量（它不計數作爲一個內部節點，使得注1不適用）

3. 在算法的源節點，將過量流量降低直到在結束時，所有頂點有0流量

4. 您可以通過將所有流入流量相加並減去所有流出流量來計算超出流量。

5. 但是，在實踐中，該算法維護一個過量流的數組並隨着算法的進展更新該值。