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邊。