資源描述：
《最大流算法及其應用.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。
1、最大流算法及其應用提要網(wǎng)絡流相關的一些概念最大流和最小割問題最大流算法的應用總結一、網(wǎng)絡流相關的一些概念流網(wǎng)絡(FlowNetwork)流網(wǎng)絡是一個有向圖G=(V,E)，其中每條邊(u,v)∈E均有一非負容量c(u,v)≥0。如果(u,v)∈E，則假定c(u,v)=0。流網(wǎng)絡中有兩個特別的頂點：源點s和匯點t。圖1一個流網(wǎng)絡的例子stv1v4v5v2v3v635221642314流(Flow)G的流是一個實值函數(shù)f，f(u,v)表示頂點u到頂點v的流，它可以為正，為零，也可以為負，且滿足下列三個性質：容量限制：對所有u,v∈V，要求f(u,v)≤c(u,v)。反
2、對稱性：對所有u,v∈V，要求f(u,v)=-f(v,u)。流守恒性：對所有u,v∈V-{s,t}，要求流量整個流網(wǎng)絡G的流量：割(Cut)流網(wǎng)絡G=(V,E)的割(S,T)將劃分成S和T=V-S兩部分，使得s∈S，t∈T。定義割(S,T)的容量為c(S,T)，則：殘留網(wǎng)絡(ResidualNetwork)給定一個流網(wǎng)絡G=(V,E)和流f，由f壓得的G的殘留網(wǎng)絡Gf=(V,Ef)，定義cf(u,v)為殘留網(wǎng)絡Gf中邊(u,v)的容量。如果弧(u,v)∈E或弧(v,u)∈E，則(u,v)∈Ef，且cf(u,v)=c(u,v)-f(u,v)。在下面的各種概念和方法
3、中，我們只考慮殘留網(wǎng)絡中容量大于0的弧，但是編程時為了方便還是保留了。增廣路徑(AugmentingPath)對于殘留網(wǎng)絡Gf中的一條s-t路徑p稱其為增廣路徑，定義增廣路徑p的殘留容量為p上弧容量的最小值。后面求最大流要用到增廣路徑這個概念。增廣(Augment)對于殘留網(wǎng)絡Gf中的一條增廣路徑p，增廣的意思就是對于每一條屬于p的弧(u,v)，將f(u,v)增加p的殘留容量，將f(v,u)減少p的殘留容量。這樣的話，新的流f仍然滿足流的三條性質，并且原流網(wǎng)絡的流量
4、f
5、增加了。一般來說，增廣過后就會修改殘留網(wǎng)絡，易得對于每一條屬于p的弧(u,v)，要將cf(u
6、,v)減去p的殘留容量，cf(v,u)加上p的殘留容量。（程序實現(xiàn)基本都是通過直接修改殘留網(wǎng)絡來實現(xiàn)增廣的）二、最大流和最小割問題最大流問題對于一個流網(wǎng)絡G=(V,E)，其流量
7、f
8、的最大值稱為最大流，最大流問題就是求一個流網(wǎng)絡的最大流。增廣路定理當且僅當由當前的流f壓得的殘留網(wǎng)絡Gf中不存在增廣路徑時，流f的流量
9、f
10、達到最大。（證明在此略去，可以參見相關書籍）根據(jù)增廣路定理，我們可以設計出最基本的求最大流的方法，一開始將流網(wǎng)絡G=(V,E)的流f置為零流，即對于(u,v)∈E時，f(u,v)=0。然后構建殘留網(wǎng)絡，尋找增廣路徑增廣，再修改殘留網(wǎng)絡，重復此過程
11、，直到無法找到增廣路徑。此方法（之所以不是算法，是因為實現(xiàn)方法很多）稱為Ford-Fulkerson方法。Ford-Fulkerson方法的偽代碼FORD-FULKERSON-METHORD(G,s,t)1initializeflowfto02whilethereexistsanaugmentingpathp3doaugmentflowfalongp4returnf最小割問題最小割是指流網(wǎng)絡中容量最小的割。Ford-Fulkerson定理（最小割最大流定理）：在流網(wǎng)絡中，最小割的容量等于最大流的流量。（證明也在此略去）根據(jù)這個定理，我們就可以通過求流網(wǎng)絡的最大流
12、來得到最小割。最大流算法前面所講的只是求最大流的一種方法，但怎樣高效地實現(xiàn)還是一個問題。這個方法的最大問題就在于怎樣快速地找到一條增廣路徑。當然我們可以用最基本的搜索（DFS或BFS），但是這種方法肯定不夠高效，這時我們就需要更高效的算法。本文將重點介紹一種高效且實用的最大流算法：SAP算法（最短增廣路算法）。最短增廣路算法即每次尋找包含弧的個數(shù)最少的增廣路進行增廣，可以證明，此算法最多只需要進行mn/2次增廣。并且引入距離標號的概念，可以在O(n)的時間里找到一條最短增廣路。最終的時間復雜度為O(n2m)，但在實踐中，時間復雜度遠遠小于理論值（特別是加了優(yōu)化之
13、后），因此還是很實用的。（此段中n表示頂點數(shù)
14、V
15、，m表示邊數(shù)
16、E
17、）距離標號對于每個頂點i賦予一個非負整數(shù)值d(i)來描述i到t的“距離”遠近，稱它為距離標號，并且滿足以下兩個條件：d(t)=0對于殘留網(wǎng)絡Gf中的一條弧(i,j)，d(i)≤d(j)+1。允許弧和允許路如果殘留網(wǎng)絡Gf中的一條弧(i,j)滿足d(i)=d(j)+1，我們稱(i,j)是允許弧，由允許弧組成的一條s-t路徑是允許路。顯然，允許路是殘留網(wǎng)絡Gf中的一條最短增廣路。當找不到允許路的時候，我們需要修改某些點的d(i)。算法基本架構ProcedureShortest_Augmenting_
18、Path;Var……Be
