ISAP全稱Improved Shortest Augmenting Path，意指在SAP算法進行優(yōu)化。SAP即Edmonds-Karp算法，其具體思路是通過不斷向殘存網(wǎng)絡推送流量來計算整個網(wǎng)絡的最大流。閱讀本文要求掌握網(wǎng)絡流的基礎概念，不懂的出門左拐算法導論。ISAP的時間復雜度與EK算法一致，而EK算法的時間復雜度為min(O(E|f|),O(VE^2))，其中O(E|f|)部分是因為其是在FORD-FULKERSON算法上的改進。EK算法在FF算法的基礎上將隨意取增廣路徑替換為取最短增廣路徑，而ISAP在EK算法的基礎上剔除了除了第一次外的后續(xù)廣度優(yōu)先搜索尋找最短路徑的部分。下面對ISAP算法進行說明。

　　先說明一些名詞，稱殘存網(wǎng)絡中容量非0的邊為有效邊。

　　我們首先在EK算法的基礎上，為每個頂點添加新的屬性d，表示其到匯點t的最短路徑（路徑只能包含有效邊），這個最短路徑是基于殘存網(wǎng)絡的，而非原圖，因此d屬性會隨著流的推送導致殘存網(wǎng)絡的變更而變更。顯然要維護這樣一個屬性d，每次在推送流后，都需要基于新形成的殘存網(wǎng)絡重新執(zhí)行廣度優(yōu)先搜索算法，以計算每個頂點正確的d屬性，這樣不就與EK算法完全一樣了嗎？是的，因此為了避免每次流推送都必須重新計算最短路徑，我們需要修改d的定義，d表示頂點到t的距離的某個下界。為了說明這樣定義之后就不用再每次重新執(zhí)行廣度優(yōu)先搜索算法計算d，只需要說明每次向殘存網(wǎng)絡推送流，只會導致每個頂點到t的距離非嚴格遞增：

　　證明：假設我們向圖G沿最短路徑推送流，并形成新圖G'。我們記R(a,b)表示原圖中從點a到點b的最短距離，記R'(a,b)表示在新圖（殘存網(wǎng)絡）中a到b的最短距離。我們所要證明的就是對于任意點x都有R(x,t)<=R'(x,t)。假設存在點x，滿足R(x,t)>R'(x,t)，顯然x到t的最短路徑之中必然包含由于流推送而新增的邊，假設(v,u)是圖G'中x到t中距離點x最近的新增邊，而(u,v)是處于G中最短增廣路徑上。這樣我們就可以把G'中的x到t的最短路徑寫作x,...,v,u,...,t，顯然R'(x,v)=R(x,v)，因為其中不含新增邊和刪除邊（即與G上的最短增廣路徑無交集）。由于R'(x,t)<R(x,t)可得R'(v,t)<R(v,t)，從而有R'(u,t)<R(u,t)，因此由前面的說明可知存在增廣路徑的邊(q,w)，使得(w,q)存在于R'(u,t)代表的最短路徑中。利用同樣的思路證明下去我們可以得到無窮多的增廣路徑上的邊出現(xiàn)在了R'(x,t)對應的路徑之中，而由于一條最短路徑是不可能包含重復邊，且所有不同邊的總數(shù)最多只有2*|E|條（正向邊以及逆向邊），因此這與R'(x,t)是最短路徑這一性質(zhì)相悖，故假設不成立，因此R'(x,t)>=R(x,t)。

　　繼續(xù)說明流程的執(zhí)行。由于d是描述一個頂點距離t的下界，因此當一個頂點的屬性d超過|V|時，這個頂點將永遠無法推送流到t（最短路徑不含相同頂點的簡單應用）。而我們可以以源點s的屬性d是否超過|V|來作為結束推送的條件。具體流程是我們循環(huán)推送，每次都從s開始向其余所有與s相鄰且d屬性為s.d-1的頂點推送無窮的流。我們期望這樣的流推送成功當且僅當增廣路徑上的頂點序列的d屬性為s.d,s.d-1,...,1,0，否則推送就不應該成功。顯然在推送成功的情況下，由于d是距離下界，因此推送路徑一定是最短的增廣路徑。而所謂的推送失敗是指抵達一個頂點x（非t），所有鄰接的可抵達頂點（指存在有效邊連接）的距離都不等于x-1，這意味著附近的所有頂點到t的距離都由于前面對流的推送而增大了，因此我們也應該對x的距離進行增大（因為一個頂點距離t的最短距離應該是其與可以通過有效邊連接的所有頂點到t的最短距離的最小值+1），由于周邊的所有頂點的d屬性均>=x.d，因此我們將x.d賦值為x.d+1也是合適的，不會違背我們對d的定義，在我們修改了d的值之后，顯然這與我們期望的可推送的增廣路徑已經(jīng)不相符了，因為d屬性為x.d+1的頂點出現(xiàn)了兩次，因此我們宣告失敗回到之前的頂點。而當我們推送成功且x是方才推送的增廣路徑上的某個頂點，且此時從前面頂點傳來的流還足夠支持下次推送，那么我們可以繼續(xù)尋找其滿足d屬性為x.d-1的后繼頂點，繼續(xù)推送（這也是ISAP的優(yōu)化之一）。

　　先說明程序會正確停止。由于推送成功就意味著存在增廣路徑（而且是符合嚴苛條件的最短增廣路徑），此時顯然還可以繼續(xù)通過向增廣路徑推送流來獲得最大流。當我們發(fā)現(xiàn)不存在增廣路徑時，即s向周邊推送失敗，我們會不斷增大s.d屬性，而當s.d>|V|時，我們就結束推送，此時程序正確結束。

　　時間復雜度與EK基本一致，只是將其中原本每次成功推送后執(zhí)行廣度優(yōu)先搜索去掉，取而代之的是增加了推送失敗情況下對頂點d屬性的增大。由于一個頂點d屬性不會超過|V|，因此我們可以保證每個頂點d屬性最多增大|V|次，而總共有|V|個頂點，因此失敗處理次數(shù)不會超過|V|^2。同時由于我們每次推送成功時也會遍歷大量的不同邊和不同頂點，這個流程在最糟糕的情況下的時間復雜度為O(|V|+|E|)，與廣度優(yōu)先搜索算法一致，因此算法上界應該為O(VE^2+V^2)=O(VE^2)，與EK算法一致。

　　ISAP有一個通用的GAP優(yōu)化就是我們將擁有不同d屬性值的頂點進行分組，以d屬性值作為編號。當我們修正一個頂點p的d屬性值（推送失敗時），我們可以通過判斷p.d這一組元素是否只有一個，當只有一個時，意味著我們再修改p.d為p.d+1后，p.d這一組將會為空，這是一個好消息，因為后面所有從s發(fā)出的推送請求都會由于沒有p.d組的頂點可以接受請求而失敗，因此我們可以斷定此時殘存網(wǎng)絡中的流即是最大流，我們可以通過提前將s.d修改為|V|來跳過后面一系列的失敗處理，從而優(yōu)化性能。

　　下面給出代碼：

　　

bfs(t) //從t開始進行廣度優(yōu)先搜索，如果頂點v到t無路徑，則v.d=-1
　　for v in V
　　　　v.d=-1　　　t.d = 0que = empty-queueque.enque(t)while(!que.isEmpty())head = que.deque()group[head.d]+=1for edge in head.edgeListif(edge.isNegative)//只允許沿著有效邊的反向邊移動if(edge.dst.d == -1)edge.dst.d = head.d + 1que.enque(edge.dst)sendFlow(node, flowLimit) //通過頂點node向周圍最多推送flowLimit單位的流，如果推送量為0，則表示推送失敗total = 0for edge in node.edgeListif(edge.capacity > edge.flow && edge.dst.d == node.d - 1) //發(fā)現(xiàn)符合條件的有效邊actually = sendFlow(edge.dst, min(flowLimit, edge.capacity - edge.flow)flowLimit -= actually
　　　　　　　edge.sendFlow(actually);total += actually
　　　　　　　if(flowLimit == 0)
　　　　　　　　　breakif(total == 0) //如果發(fā)送失敗group[node.d]-=1if(group[node.d] == 0) //發(fā)現(xiàn)斷層s.d = |V| node.d+=1group[node.d]+=1return totalisap(s, t)bfs(t)if(s.d == -1)//如果從s到t不存在路徑return 0sum = 0while(s.d < |V|)sum += sendFlow(s, INF)
　　 return sum

?

轉(zhuǎn)載于:https://www.cnblogs.com/dalt/p/7944848.html

總結

以上是生活随笔為你收集整理的ISAP网络流算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。