一種新的增廣路徑最大流算法

李江龍 馬詩貴

（遵義醫科大學計算機網絡管理中心 貴州省遵義市 563000）

1 引言

“網絡流理論”是在20 世紀50 年代由Ford-Fulkerson 兩人建立的，是網絡應用的重要組成部分，1955 年，最大流問題在鐵路運輸行業被首次提出，在1956 年，Ford-Fulkerson 又創建了最大流理論，首次提出了“最大流，最小割”的重要學說，給出了解決最大流問題的算法。

目前，最大流算法分成兩大類，第一類是增廣路徑算法，包含Ford-Fulkerson 算法[1]，Edmond-Karp[2]算法以及Dinic[3]算法等；第二類是預流推進算法，典型的有FIFO 預流推進算法和HLLP 算法等。

本文主要研究增廣路徑算法的改進方法。在增廣路徑算法中，由于算法本身的缺陷，導致對于路徑的選擇存在隨機性，加上我們采用了貪婪算法求解最大流，所以在開始尋找增廣路徑時并沒有考慮到全局最優選擇，即便采用了最優選擇，在某些特定的情況下，仍然會造成在找到正確的最大流之前，網絡圖提前失去連通性，這是一個影響算法正確性的致命問題。為了解決問題，我們必須犧牲算法的效率，尋找通用性較高的方法，保障算法的正確性。以往的最大流算法利用反向邊思路提供一個反悔機制[4]，通過將錯誤占用的邊以及流量退還，給算法一個重新選擇路徑的機會，選出不會導致網絡圖提前失去連通性的增廣路徑，這種方法能很好的解決上述問題，但是另一方面，算法的復雜度也由于反悔帶來的多余步驟而上升。本文提出一種新的增廣路徑最大流算法，關鍵頂點可行分量算法（KPFC），引入關鍵頂點機制，將其去除，從而求出網絡圖的可行分量，再在可行分量中尋找增廣路，從而簡化路徑尋找的難度，替代反向邊機制，有效降低算法復雜度。

2 基本概念

2.1 （容量）網絡[5]

在有向連通圖D=(V,E)中，記（容量）網絡為G=(V,E,c)，需滿足：

（1）在D 中存在特定的兩個頂點，分別為源點與匯點；對于D 中的中間節點必須是同時具有入弧和出弧的節點。

2.2 流量、容量和可行流[5]

流量是指鏈路上正在流過的數據量，通常用f(u,v)來表示，u,v是兩個頂點的編號，流量可以是管道中的水量，也可以是道路中的車流量等；容量是指鏈路的最大承載量，通常用c(u,v)來表示；可行流是指滿足條件的流量。

2.3 增廣路徑[5]

增廣路徑是指連通源點和匯點的一條路徑，這條路徑上的所有正向邊都滿足反向邊滿足這樣的路徑叫做增廣路徑。

2.4 殘存網絡[5]

圖1：KPFC 算法流程圖

2.5 距離標號和允許弧[5]

2.6 最大流問題的數學模型[5]

那么fst成為容量網絡G 的全部可行流的其中之一，若此流的值為全部可行流中的最大值，則此流叫做最大流，記為fmax。在上式中符合條件的弧叫做飽和弧，符合條件的弧叫做非飽和弧。可行流符合流守恒定律，表現在源點S 流出的全部流量都能夠通向匯點T 并且被全部接收；除了源點S 與匯點T，全部的中間節點都只起到流通流量的作用。

3 算法描述

3.1 算法步驟

（1）根據原網絡圖創建結構體數組。

（2）找出并記錄關鍵頂點，構建可行分量。

（3）利用DFS 算法在可行分量中尋找增廣路徑。

（4）若可行分量仍然連通，返回步驟（3），若可行分量不連通，刪除無用頂點（若存在），判斷是否存在關鍵頂點，若存在，加入關鍵頂點，返回步驟（2）；若不存在，則算法結束。

KPFC 算法的流程圖如圖1 所示。

3.2 算法分析

關鍵頂點可行分量算法，又稱KPFC 算法，該算法的改進在于取消了反向邊機制，屬于增廣路徑算法，利用一維結構體數組來存儲網絡圖，引入關鍵頂點來構建網絡圖的可行分量，解決路徑選擇不合理等相關問題。所謂關鍵頂點，即去除之后在保障圖的連通性的前提下，能夠最大限度的將原圖簡化的頂點，關鍵頂點的確定滿足以下幾個條件之一：第一，入弧和出弧數量之和大于2；第二，入弧或出弧數量小于1；第三，鄰接點數量小于2。 在判定一個滿足上述條件的頂點為關鍵頂點之前，需對去除此頂點后，是否會使網絡圖失去連通性做出判斷，若不影響圖的連通性，才將頂點判定為關鍵頂點，在網絡圖中，若存在多條增廣路徑，那么這些路必定會經過關鍵頂點一次或多次，關鍵頂點不止一個，在將所有關鍵頂點都去掉之后，我們能夠得到一張最簡化的連通圖，這個圖便稱為原網絡圖的一個可行分量。 在尋找增廣路徑時，如果發現圖不再連通，判斷可行分量中的頂點是否還有剩余容量不為零的入弧和出弧，若一個頂點的所有入弧或出弧的剩余容量為零，便將此頂點判定為無用頂點，可將其刪除，后續計算無需再考慮此頂點。再加入擁有最多鄰接點的關鍵頂點，優先消耗此類（鄰接點最多）頂點的弧的剩余容量，可以快速的減小原網絡圖的復雜程度，加入關鍵頂點后，繼續尋找新的關鍵頂點，可以形成新的可行分量，進而尋找增廣路徑，這樣重復執行，直到所有關鍵頂點都被加入，就能找出最大流。

3.3 算法實例分析

有圖如圖2 所示，求其最大流：

將圖2 用一維結構體數組方式表示為：

本算法采用鄰接矩陣來表示圖，在具體代碼里，用一個結構體一維數組來體現，假設圖包含n 個頂點，數組的元素數量即為n 個，每一個元素都是一個結構體，表示一個頂點，其中包含四個參數，分別表示頂點的父頂點，子頂點，入弧容量和出弧容量，每一個參數都是一個一維數組，因為一個頂點可能存在多個父頂點或子頂點。如上所示，從上到下分別為S、A、B、C、D、T 頂點的滿足條件的鄰接點和弧的容量，由于S 頂點沒有父頂點，所以其參數用-1 來表示，T 頂點的參數同理，圖中有兩個關鍵頂點，分別為A 和C，關鍵頂點用一個一維數組kpoint 來表示，此時，kpoint={A,C}，在去掉這兩個關鍵頂點之后，原圖變成如下所示：

這是一個可行分量，只能找到一條增廣路徑，就是S-B-D-T，當前流量為路徑上的最小容量，即為2，設最大流為SUM，當前最大流SUM=2。

此時找不到增廣路徑，我們在圖中加入擁有最多鄰接點的關鍵頂點A（頂點A 和C 的鄰接點數量一樣，按照順序添加），此時kpoint={C}，圖變為如下所示：

此時可以找到新的關鍵頂點B，加入到kpoint 數組，kpoint= {C,B}，構建新的可行分量，如下所示：

找到一條增廣路徑，即為S-A-D-T，當前路徑流量為4，所以SUM=2+4=6。

此時A 點所有入弧容量為零，判定為無用頂點，直接刪除，找不到新的增廣路徑，加入關鍵頂點C，圖變成如下所示：

圖不連通，查看是否還有關鍵頂點，存在關鍵頂點B，將其加入圖變成如下所示：

此時可以找出一個關鍵頂點D，去除后，圖變成如下所示：

找到一條增廣路徑為：S-B-C-T，當前路徑可行流為2，最大流SUM=6+2=8。

圖失去連通性，加入最后一個關鍵頂點D，圖變為如下所示：

到此，網絡圖不再連通，并且不存在關鍵頂點，算法結束，最大流為8。

3.4 實驗

對比傳統算法與KPFC 算法求解圖3 的最大流的區別：

算法代碼采用C++語言開發，在Visual studio 2019 環境下進行編譯運行，下列運行結果均為Visual studio 2019 真實運行結果截圖。

圖2：KPFC 算法例圖

圖3：KPFC 算法例圖

圖4

Isap 算法求解片步驟如下：

首先初始化距離標號和進行GAP 優化的num 數組。

此圖一共7 個頂點，從頂點1 到7 的距離標號分別為：3,2,2,2,1,1,0，可以看出，距離標號1 的數量是2，2 的數量是3，3的數量是1，然后結合距離標號尋找第一條增廣路徑。

第一條增廣路徑為1-4-6-7，更新距離標號及num 數組。

從源點到匯點的距離標號分別更新為：3,2,2,4,1,1,0，可以看出，距離標號1 的數量是2，2 的數量是2，3 的數量是1，4 的數量是1.更新距離標號以及num 的步驟（除了初始化距離標號）重復了5 次，找到的增廣路徑分別為：1-3-6-7，1-3-5-7，1-2-5-7，1-3-6-5-7，最終找出正確的最大流，如圖4 所示。

KPFC 算法求解步驟如下：

首先尋找關鍵頂點。

找到三個關鍵頂點分別為2，3 和5，kp={2,3,5}開始尋找增廣路徑。

第一條增廣路徑為1-4-6-7，發現頂點4 變為無用頂點并且圖失去連通性，加入擁有最多鄰接點的關鍵頂點3，此時kp={2,5}繼續尋找增廣路徑。

找到的第二條增廣路徑為1-3-6-7，發現圖失去連通性，加入關鍵頂點5，在此基礎上繼續找到新的關鍵頂點6，此時kp={2,6}繼續尋找增廣路徑。

尋找到第三條增廣路徑為1-3-5-7，圖失去連通性，加入關鍵頂點6，此時kp={2}，繼續尋找增廣路徑。

找到的第四條增廣路徑為1-3-6-5-7，發現頂點6 變為無用頂點并且圖失去連通性，加入關鍵頂點2，在此基礎上找到新的關鍵頂點3，此時kp={3}，繼續尋找增廣路徑。

加入頂點2 之后，尋找到第五條增廣路徑為1-2-5-7，圖失去連通性，加入關鍵頂點3，繼續尋找增廣路徑，發現圖失去連通性，并且不存在關鍵頂點，算法結束。

得到正確的最大流為14，與ISAP 算法相比，KPFC 算法去掉了距離標號的初始化，減少了每找到一條增廣路徑后，對距離標號的計算步驟，KPFC 算法增加了每次找到增廣路徑后對關鍵頂點的尋找，而并不是每一次尋路之后都有新的關鍵頂點，所以總的來說，KPFC 算法優于Isap 算法[6]。

4 結束語

未來對于最大流問題的研究還需考慮遍歷算法的改進，讓算法具有更聰明的預判能力，盡量減少尋找增廣路徑的隨機性。本文主要對反向邊機制做出了改進，沒有對增廣路徑的尋找進行深度優化，在以后的研究中，多條增廣路徑，可結合最大可行流的概念，做出最優的選擇，進一步提高算法效率，總體原則為，用最少的計算步驟，達到問題的最大簡化效果。在公共資源越發緊缺的情況下，算法與實際情況的結合，算法在實際問題中的部署與應用，是我們今后應該努力的方向，畢竟能夠解決實際問題，才是研究算法真正的意義所在。