最大流的算法——Edmonds-Karp算法(最短路徑增廣算法)

這里介紹一個最簡單的算法:Edmonds-Karp算法 即最短路徑增廣算法 簡稱EK算法

EK算法基于一個基本的方法:Ford-Fulkerson方法 即增廣路方法 簡稱FF方法

增廣路方法是很多網(wǎng)絡(luò)流算法的基礎(chǔ) 一般都在殘留網(wǎng)絡(luò)中實現(xiàn)

其思路是每次找出一條從源到匯的能夠增加流的路徑 調(diào)整流值和殘留網(wǎng)絡(luò) 不斷調(diào)整直到?jīng)]有增廣路為止

FF方法的基礎(chǔ)是增廣路定理(Augmenting Path Theorem):網(wǎng)絡(luò)達(dá)到最大流當(dāng)且僅當(dāng)殘留網(wǎng)絡(luò)中沒有增廣路

要實現(xiàn)這個算法，就遇到了三個問題：

(1)最多要增廣多少次?

可以證明 最多O(VE)次增廣 可以達(dá)到最大流 證明略

(2)如何找到一條增廣路?

先明確什么是增廣路: 增廣路是這樣一條從s到t的路徑 路徑上每條邊殘留容量都為正

把殘留容量為正的邊設(shè)為可行的邊 那么我們就可以用簡單的BFS得到邊數(shù)最少的增廣路

(3)BFS得到增廣路之后 這條增廣路能夠增廣的流值, 是路徑上最小殘留容量邊決定的

把這個最小殘留容量MinCap值加到最大流值Flow上, 同時路徑上每條邊的殘留容量值減去MinCap

最后,路徑上每條邊的反向邊殘留容量值要加上MinCap

看一個具體的增廣路算法的例子吧