李曉明

在高速公路網(wǎng)中有車流，在互聯(lián)網(wǎng)上有信息流，在自來水管網(wǎng)中有水流，在公用電網(wǎng)中有電流，等等。但凡網(wǎng)絡(luò)，大都和某種流聯(lián)系在一起;網(wǎng)絡(luò)的作用，就是要保障那些流的暢通。對網(wǎng)絡(luò)中流的研究是具有普遍意義的主題。

研究網(wǎng)絡(luò)中的流問題可有多個不同的視角和目標(biāo)追求。本文討論兩個節(jié)點之間可能經(jīng)過的最大流量。我們從簡單例子開始，建立討論這個話題的語境。

圖1所示為一個3節(jié)點{s，a，t}的有向網(wǎng)絡(luò)，邊上的數(shù)字表示能支持的流量（不妨看成是單位時間能通過的車輛數(shù)），一般也稱為對應(yīng)邊的“容量”。這個例子數(shù)據(jù)表明s—a邊的容量為3，a—t邊的容量為2。想象為道路，也就相當(dāng)于是說s—a路段要比a—t路段寬一些。邊的箭頭方向則表示“單行線”的方向。

現(xiàn)在的問題是，如果我們要不斷從s發(fā)出開往t的車，單位時間能發(fā)多少輛？幾乎不用多想，你馬上會認(rèn)識到3是不行的，最多是2。而且如果有人說1，你則會說每條邊的容量都還有剩余，因而流量還可以增加。于是我們說，2就是這個網(wǎng)絡(luò)中從s到t的最大流量。并且，如果面對的不止兩個路段，而是多個如此串聯(lián)的路段，你也能認(rèn)識到從s到t的最大流量受限于最小容量的路段。那樣的路段，也稱為“瓶頸”，別的路段再寬也沒有用。在本專欄前兩期討論調(diào)度問題時，我們有過一個背景不同但精神上有類似之處的概念，就是“關(guān)鍵路徑”，它就是完成任務(wù)的瓶頸。下面考慮圖2所示的一個稍微復(fù)雜一點的例子。

先看圖2（a），不妨也看成是一個道路網(wǎng)的抽象。在討論流問題時，總假設(shè)有一個節(jié)點是出發(fā)點，習(xí)慣上用s表示，畫在圖的最左端，還假設(shè)一個節(jié)點為到達(dá)點，用t表示，畫在圖的最右端。這個網(wǎng)絡(luò)中還有另外兩個節(jié)點a和b，以及節(jié)點之間的5條路段，它們的容量也相應(yīng)標(biāo)在上面。在圖2（a）中，我們還看到有3條從s到t的路徑：s—a—t，s—b—t和s—a—b—t。

單位時間里從s到t能發(fā)出多少輛車？顯然取決于那些車走的路徑。如果讓它們都走s—a—b—t，如圖2（b）所示，那最多是20。此時路段s—b用不上了，因為它后面的b—t已經(jīng)被占滿。不過，如果我們讓20輛走s—a，但在a分流，10輛走a—t，10輛走a—b，同時讓10輛走s—b—t，就實現(xiàn)了從s到t的最大流量30。圖2（c）所示的，是這樣一種安排的另一個視角的理解，虛線所表示的相當(dāng)于是說在圖2（b）已經(jīng)在s—a—b—t安排了流量20的基礎(chǔ)上，可以讓從s—b來的流量（10）沿著a—b的反方向到達(dá)t。這樣一種視角和前面說的在a點分流是等價的，它乍聽起來不如分流的說法自然，但方便地成為我們后面討論算法的“思想基礎(chǔ)”。

到此，讀者應(yīng)該慢慢體會到這個問題的挑戰(zhàn)之處了，如果網(wǎng)絡(luò)稍微復(fù)雜一點，如圖3（a）所示，要目測得出源s到目的t之間最大流量的安排絕非易事，因而需要算法。

首先，讓我們來一般地理解一下這個問題。給定一個如圖3（a）所示的網(wǎng)絡(luò)，假設(shè)需要在每條邊上做流量安排，總體體現(xiàn)為從s到t的流量。如果有人說他做了一個如圖3（c）的安排（現(xiàn)在每條邊上標(biāo)有兩個數(shù)，第一個為容量，第二個括弧中的數(shù)表示流量安排），你會有什么觀感？首先，你會馬上說“不靠譜”，因為在a—b邊上他安排的是13，要大于網(wǎng)絡(luò)中a—b的容量12，這是不可接受的。還有沒有別的問題？還有一個也是不可接受的問題！注意節(jié)點c，進(jìn)入它的流是12+0+0=12，而離開它的流是3+11=14，二者不相等，是矛盾的。也就是說，任何“可行的”安排必須滿足兩個條件：①每條邊上流量分配不能超過邊的容量;②除了出發(fā)點s和結(jié)束點t外，每個節(jié)點的“入流”必須等于“出流”。

現(xiàn)在你可以看看圖3（b）了。有什么問題嗎？它滿足上述兩個條件，于是我們說它是一個“可行解”，對應(yīng)的總流量為11，但我們不知道它是不是“最優(yōu)解”（即對應(yīng)s—t之間的最大流安排）。事實上，對這個例子而言，你容易看到沿著s—a—b—t的流量并沒有用盡，三條邊上分別還剩16-8=8，12-6=6，20-7=13。這意味著你可以對那條路徑上的流量給一個增量min（8，6，13）=6。于是得到了一個較優(yōu)的可行解（此時s—a上的流量為14，a—b上的流量為12，b—t上的流量為13，總流量為17），但還是不知道是否最優(yōu)。

的確，在此基礎(chǔ)上我們進(jìn)一步還看到一種增加流量的可能，類似于圖2（c），此時可以在s—c上增加5，在b—c上減少5，在b—t上增加5，從而得到總流量22。也就是說，如果我們在一個可行解基礎(chǔ)上發(fā)現(xiàn)一條從s到t的包含兩個不同方向邊的路徑，在順方向邊上的容量剩余，在逆方向邊上的流量均大于0，就意味著可以得到一個總流量的提升。

上述在一個可行解的基礎(chǔ)上有兩種改進(jìn)思路的例子值得一般性討論，是本文要介紹的經(jīng)典Ford-Fulkerson算法（1956年發(fā)明）的關(guān)鍵。參考圖4，假設(shè)在一個可行解基礎(chǔ)上發(fā)現(xiàn)了一條如圖4（a）所示的路徑s—a—b—c—d—t，邊上的標(biāo)記x（y）表示容量為x，在當(dāng)前可行解中已經(jīng)分配了流量y，那么剩余可用的容量就是x-y。于是我們看到8-3=5，6-5=1，7-2=5，4-3=1和5-1=4，其中的最小值1就是還可以做的改進(jìn)。邊上的標(biāo)記就更新為8（4），6（6），7（3），4（4）和5（2）。顯然，結(jié)果依然是一個可行解。

假設(shè)發(fā)現(xiàn)了一個如圖4（b）所示的情況呢？注意a和b之間、c和d之間邊的方向是反過來的，因而現(xiàn)在不能說在圖中發(fā)現(xiàn)了“一條從s到t的（有向）路徑”。觀察節(jié)點a，s—a邊產(chǎn)生的入流量為3，b—a邊產(chǎn)生的入流量為5，加起來是8。由于是可行解，在a上的入流之和要等于出流之和，因此這個8一定已被與a相關(guān)的其他出向邊抵消掉了。此時，如果我們讓s—a上的流量“+1”，讓b—a上的流量“-1”，不會打破在節(jié)點a上的流量平衡，但破壞了節(jié)點b上的流量平衡——出流少了1。怎么辦？讓b—c邊上的流量“+1”就可以了，但這又導(dǎo)致節(jié)點c上的入流多了1，解決的辦法是讓d—c上的流量“-1”，又造成d上的出流少了1，最后就靠在d—t上“+1”補償，從而完成整個平衡，得到了一個總流量提高的可行解。值得指出的是，類似于圖4（b）的路徑上的邊不一定非得是正反方向交替的。體會上述分析，我們能認(rèn)識到關(guān)鍵是保持每個中間節(jié)點出入流量的平衡，順向邊的邊“+”，逆向的邊“-”。

對圖4（b）這個例子而言，其實改進(jìn)可以比“+1”更大。但凡需要增加流量的邊，不得超過剩余容量，但凡需要減少流量的邊，不得超過已分配的流量。因此我們看到8-3=5，5，7-2=5，3和5-1=4，其中的最小值3就是可以得到的最大改進(jìn)。

綜上所述，F(xiàn)ord-Fulkerson算法的基本思想就是從一個每條邊流量為0的初始狀態(tài)（顯然是一個可行解）開始，不斷發(fā)現(xiàn)上述兩種改進(jìn)的機會，直至沒有新機會了。

第一種機會，就是要看能否找到一條從s到t的有向路徑，其上每一條邊的剩余流量都大于0。第二種機會，就是要看能否找到一條從s到t的邊方向不一定一致的路徑（但一定是離開s，進(jìn)入t），其上順邊的剩余流量和逆邊的流量都大于0。道理上就是這樣的，不過后者實施起來會感覺別扭。為此，人們想出了一個好辦法：將第二種情況轉(zhuǎn)變?yōu)榈谝环N，從而可以統(tǒng)一處理。還是以圖4為例，這個辦法體現(xiàn)在圖4（c）中，我們特別注意其中增加了兩條邊a—b和c—d，上面標(biāo)示的容量分別為b—a和d—c邊上已分配的流量。這樣一來，在原始圖上存在一條邊方向不一致的路徑，就等價于在新的圖上存在一條有向路徑了。與第一種所有方向一致的情況一道，這樣的路徑統(tǒng)一稱為“增量路徑”（augmenting path）。

在程序?qū)崿F(xiàn)中的具體做法就是，用A表示原始網(wǎng)絡(luò)，但在算法過程中操作一個所謂剩余容量網(wǎng)絡(luò)G。最初讓G=A，一旦決定G的某條邊a—b上要分配一個流量x，那么除了在a—b當(dāng)前剩余容量上減x，同時也在b—a的容量上加x。這樣，在當(dāng)前可行解上尋找提升流量的機會，就都變成在G上尋找一條從s到t的增量路徑問題。我們以前面的圖2為例來看這個過程。圖5（a）是圖2所示網(wǎng)絡(luò)的鄰接矩陣A，也就是初始的G，其中下畫線的3個數(shù)字對應(yīng)找到的s—a—b—t路徑，我們看到最小值為20。于是做更新，除了每一個數(shù)減去20外，在對稱的地方（也就是反向邊）要加20，于是得到圖5（b）。

圖5（b）中下畫線的3個數(shù)字對應(yīng)找到的是增量路徑s—b—a—t，我們看到最小值為10。于是做更新，除了對應(yīng)每一個數(shù)減去10外，在對稱的地方要加10，于是得到圖5（c）。特別注意到，a—b邊上剩余流量的情況，最開始是30，然后是10，現(xiàn)在又變成20了。而b—a邊上則是0，20，10，兩條邊上對應(yīng)數(shù)據(jù)之和總是30，即原始網(wǎng)絡(luò)中邊上的容量。這正是兩種情況交替出現(xiàn)可能帶來的結(jié)果。

最后的流量分配在圖5（d）中，它是圖5（a）中的初始容量減去圖5（c）中對應(yīng)項的結(jié)果。

至此，可以說我們已經(jīng)完成了算法的描述。宏觀上即是，用給定的網(wǎng)絡(luò)A，初始化一個稱為剩余容量網(wǎng)絡(luò)的操作網(wǎng)絡(luò)G，不斷在G上發(fā)現(xiàn)從s到t的有向（增量）路徑，并按照所定的規(guī)則對G進(jìn)行更新，直到?jīng)]有s—t路徑可以發(fā)現(xiàn)了，也就是再也沒有提升可行解質(zhì)量的機會了。

怎么在G上發(fā)現(xiàn)是否存在s—t增量路徑？G是一個有向圖，廣度優(yōu)先搜索和深度優(yōu)先搜索都可以用于發(fā)現(xiàn)兩個節(jié)點之間有向路徑。在本專欄前面的文章中，我們多次用到這兩種搜索方法，在此不再單獨介紹。下面參照圖6給出一個廣度優(yōu)先搜索的程序版本，看看算法的實現(xiàn)。

先看10～18行的主程序部分。它要控制做若干次從S開始的廣度優(yōu)先搜索，每次搜索若達(dá)到了目的節(jié)點t，就更新剩余流量網(wǎng)絡(luò)G，然后繼續(xù)搜索;如果沒達(dá)到t，就意味著沒機會了，結(jié)束。結(jié)束的時候，最大流的分配方案則由初始網(wǎng)絡(luò)A和工作網(wǎng)絡(luò)G中的數(shù)據(jù)直接給出（見上面討論的圖5例）。其中每次搜索的初始化，除了一般BFS都需要的隊列（queue）和訪問與否的標(biāo)記（visited）外，還有兩個特殊的針對每一個節(jié)點的標(biāo)記——lead和flowcap。lead用于記錄搜索過程中的上層節(jié)點，flowcap用于記錄從源節(jié)點（s）經(jīng)搜索路徑到該節(jié)點的“飽和流量”。所謂飽和流量，指的是它與該路徑上至少一條邊的剩余流量相等。有了lead和flowcap，更新G就十分簡單了（因而這里沒有提供）。

BFS就是廣度優(yōu)先搜索過程，進(jìn)入時queue中有源節(jié)點s。剩余流量網(wǎng)絡(luò)G采用了矩陣表示，因而有一個for循環(huán)來看哪些節(jié)點與當(dāng)前節(jié)點x相連（G[x][i]>0）且還沒有被訪問（not visited[i]），對那些節(jié)點做BFS所需的狀態(tài)更新，并放到隊列中。第8行是和這個流量問題特別相關(guān)的，得到上面提到的飽和流量。

將這個程序用在圖3（a）數(shù)據(jù)上，得到的流量結(jié)果如圖7（a）所示。我們能夠檢驗前面指出的兩個條件，保證它是一個可行解：①每條邊上括號中的數(shù)（流量）不大于左邊的數(shù)（容量）;②每個節(jié)點的入流之和等于出流之和。這時我們看到，總流量=23，要優(yōu)于在前面討論圖3時提到的每一個可行解。同時，我們也指出一個網(wǎng)絡(luò)中最大流的具體安排不一定是唯一的，圖7（b）就是另外一種，這和在做路徑搜索時選擇節(jié)點的順序有關(guān)。

上面比較詳盡地介紹了Ford-Fulkerson算法及其程序?qū)崿F(xiàn)。作為算法研究，還有幾個問題值得考慮（下面總假設(shè)所考慮的網(wǎng)絡(luò)是有窮的，且每條邊上的容量為正整數(shù)），這里列出來并簡略討論，歡迎有進(jìn)一步興趣的讀者和我們聯(lián)系深入切磋。

（1）為什么這個算法一定會結(jié)束？在G上每找到一條新的路徑，會對一些邊的剩余容量進(jìn)行更新，有的減少，有的則是增加（如圖5所示網(wǎng)絡(luò)中a—b對應(yīng)的值），為什么一定會出現(xiàn)找不到s—t路徑的情況，從而結(jié)束算法呢？可以這樣考慮：源節(jié)點s出邊上的容量之和是有限的（不妨記C為從s出發(fā)的剩余容量，最初就是它的出邊的容量之和），算法過程中每找到一條s到t的路徑（每一條邊剩余容量都大于0），都會讓C減少，而C有下界0（盡管不一定總達(dá)到），因此算法一定會終止。

（2）即便結(jié)束，只是說在剩余流量網(wǎng)絡(luò)上找不到s—t路徑了，為什么得到的就是最大流呢？這個問題比較難一些，通常和另外一個概念“最小割”結(jié)合起來討論。給定一個我們關(guān)心的網(wǎng)絡(luò)，總可以從中刪除若干條邊，使得不再存在從s到t的有向路徑，我們稱那樣的邊集為網(wǎng)絡(luò)的“割”。每一個割邊上的容量之和就是割的容量。具有最小容量的割就是“最小割”。容易想到，任何s—t流量都不會大于最小割的容量，于是如果一個s—t流量達(dá)到了最小割容量，那它就是一個最大流。可以證明，F(xiàn)ord-Fulkerson算法終止的時候得到的就是與最小割相等的流量。

（3）算法的運行時間效率如何？從圖6的算法描述可以看到，要做若干次s—t路徑搜索。從（1）中的討論可知，次數(shù)不會超過s的出邊容量之和C。每做一次BFS，時間與網(wǎng)絡(luò)圖中的邊數(shù)（m）成正比，由于剩余容量網(wǎng)絡(luò)G的邊數(shù)每次都可能改變，但總的來說受限于節(jié)點數(shù)（n）的平方，于是可以說如此實現(xiàn)的是O（C*n2）算法。鑒于這個復(fù)雜性的表達(dá)與數(shù)值C相關(guān)，可能很大，人們也研究了另外的獨立于C的算法。

（4）雖然我們用到了圖3（a）所示網(wǎng)絡(luò)的例子，也給出了如圖7所示的結(jié)果，但在前面分析的時候沒有涉及其中既有a—c邊，也有c—a邊的情況，在程序?qū)崿F(xiàn)中需不需要做什么特別處理呢？仔細(xì)想想雙向邊的影響，能認(rèn)識到在算法中不需要做特別處理，只需對結(jié)果G中的數(shù)據(jù)做恰當(dāng)解釋，配合初始的A，就能給出最優(yōu)流量分配。

事實上，如果有雙向邊，也就是某些A[i，j]和A[j，i]都大于0，G的初始化也就有這樣的情況。按照算法，每發(fā)現(xiàn)一條路徑，其中邊的最小剩余容量值f被用來做更新，cij←cij-f，cji←cji+f。G中的任何一條邊都可能被多次發(fā)現(xiàn)在找到的路徑上，于是上述更新對同一條邊可能多次，包括反向邊j—i被發(fā)現(xiàn)，于是會做cji←cji-f，cij←cij+f。最終，G[i，j]=cij-fij+fji，G[j，i]=cji-fji+fij，其中fij表示累積的流量更新。

如何得到A上每條邊在最大流中分配的流量？看A[i，j]-G[i，j]=fij-fji和A[j，i]-G[j，i]=-（fij-fji），正好相反。哪個為正，就是在對應(yīng)邊上的分配，另一個則沒有流量分配，即流量為0。這是因為，在兩節(jié)點之間的兩個反向的邊上，總是可以讓一條邊上的流量為0。舉個例子，若算法過程產(chǎn)生了fij=8，fji=3，從節(jié)點i和j之間經(jīng)過的流量角度，等價于fij=5，fji=0。

參考文獻(xiàn)：

[1]Jon Kleinberg.Eva Tardos， Algorithm Design（影印版）[M].北京：清華大學(xué)出版社，2006，1：338-345.

[2]陳道蓄.調(diào)度問題中的算法[J].中國信息技術(shù)教育，2020（11）：25-29.

注：作者系北京大學(xué)計算機系原系主任。