最大流的算法——Edmonds-Karp算法(最短路径增广算法)
最大流的算法——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ò)達到最大流當且僅當殘留網(wǎng)絡(luò)中沒有增廣路
?
要實現(xiàn)這個算法，就遇到了三個問題：
?
(1)最多要增廣多少次?
?
可以證明?最多O(VE)次增廣?可以達到最大流?證明略
?
(2)如何找到一條增廣路?
?
先明確什么是增廣路:?增廣路是這樣一條從s到t的路徑?路徑上每條邊殘留容量都為正
?
把殘留容量為正的邊設(shè)為可行的邊?那么我們就可以用簡單的BFS得到邊數(shù)最少的增廣路
?
(3)BFS得到增廣路之后?這條增廣路能夠增廣的流值,?是路徑上最小殘留容量邊決定的
?
把這個最小殘留容量MinCap值加到最大流值Flow上,?同時路徑上每條邊的殘留容量值減去MinCap
?
最后,路徑上每條邊的反向邊殘留容量值要加上MinCap
?
?
?
看一個具體的增廣路算法的例子吧
總結(jié)
以上是生活随笔為你收集整理的最大流的算法——Edmonds-Karp算法(最短路径增广算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Edmonds_Karp 算法 (转)
- 下一篇： 程序员的快速成长之路