Edmonds-Karp具有流量能力節點的圖的算法

我正在爲有向圖實現此算法。但是關於這個圖節點的有趣的事情也有他們自己的流量能力。我認爲，原始問題的這種微妙變化必須以特殊方式處理。因爲，在原始最大流問題中，從開始到結束找到任何路徑都是可以的（實際上，在Edmonds-Karp算法中，我們需要執行BFS，並選擇到達最終節點的第一條路徑）。但是，容量擴展，我們需要更加小心'這條路徑選擇'的工作。我知道這是因爲我實現了原始算法，發現自己的流量值比最大流量小，我懷疑它是否與節點容量限制有關。Edmonds-Karp具有流量能力節點的圖的算法

我花了很多精力在這個問題上，想出了一些想法，例如通過添加自循環將初始圖形轉換爲對節點沒有容量限制的圖形（向每個節點添加自循環並查找包含此自身的路徑 - 爲路徑上的每個節點添加循環）或添加虛擬節點和邊，這些虛擬節點和邊的權重取代初始節點容量限制）但是，我不相信任何這些都是解決此問題的好方法。

任何想法將不勝感激。

在此先感謝。

來源

2012-01-05 bfaskiplar

有從最大流問題的簡單還原節點容量到正規的最大流問題：

對於在圖形中每個頂點v，與兩個頂點v_in和v_out更換。到v的每個傳入邊緣應該指向v_in，並且v的每個傳出邊緣應指向v_out。然後創建一個額外的邊緣從v_in到v_out容量c_v，容量頂點v。

所以你只需在轉換後的圖上運行Edmunds-Karp。

因此，讓我們假設你有下面的圖中你的問題（頂點v有能力2）：

s --> v --> t 
    1 2 1

這相當於該圖中的最大流問題：

s --> v_in --> v_out --> t 
    1  2   1

應該很明顯，獲得的最大流量是解決方案（並且證明也不是特別困難）。

來源

2012-01-06 00:36:00 tskuzzy

我知道它與我的最初問題沒有多大關係，但我很想知道在使用Edmonds-Karp算法之前是否有這樣的減少，我們在圖中處理循環。因爲如果處理不當，循環會以某種方式改變最大流量。我認爲，它可以是一個像你提到的減少。我們可以有一個頂點對，比如說cycle_in和cycle_out，而不是那個循環中的所有頂點，我們可以用cycle_in和cycle_out中相同容量的邊相應地替換循環頂點中的每個輸入和輸出邊。它會好嗎？ – bfaskiplar 2012-01-06 20:18:11

我忘了告訴（cycle_in，cycle_out）邊緣的容量。它必須是所有舊邊緣和節點容量的最小值。但是，我的膽子裏有一種感覺，這是一個循環圖的最大流問題的錯誤構造。 – bfaskiplar 2012-01-06 20:24:26

Edmonds-Karp具有流量能力節點的圖的算法

回答

相關問題