李曉明

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

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

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

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

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

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

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

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

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

的確，在此基礎(chǔ)上我們進(jìn)一步還看到一種增加流量的可能，類似于圖2（c），此時(shí)可以在s—c上增加5，在b—c上減少5，在b—t上增加5，從而得到總流量22。也就是說(shuō)，如果我們?cè)谝粋€(gè)可行解基礎(chǔ)上發(fā)現(xiàn)一條從s到t的包含兩個(gè)不同方向邊的路徑，在順?lè)较蜻吷系娜萘渴Ｓ?，在逆方向邊上的流量均大?，就意味著可以得到一個(gè)總流量的提升。

上述在一個(gè)可行解的基礎(chǔ)上有兩種改進(jìn)思路的例子值得一般性討論，是本文要介紹的經(jīng)典Ford-Fulkerson算法（1956年發(fā)明）的關(guān)鍵。參考圖4，假設(shè)在一個(gè)可行解基礎(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é)果依然是一個(gè)可行解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

事實(shí)上，如果有雙向邊，也就是某些A[i，j]和A[j，i]都大于0，G的初始化也就有這樣的情況。按照算法，每發(fā)現(xiàn)一條路徑，其中邊的最小剩余容量值f被用來(lái)做更新，cij←cij-f，cji←cji+f。G中的任何一條邊都可能被多次發(fā)現(xiàn)在找到的路徑上，于是上述更新對(duì)同一條邊可能多次，包括反向邊j—i被發(fā)現(xiàn)，于是會(huì)做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），正好相反。哪個(gè)為正，就是在對(duì)應(yīng)邊上的分配，另一個(gè)則沒(méi)有流量分配，即流量為0。這是因?yàn)?，在兩?jié)點(diǎn)之間的兩個(gè)反向的邊上，總是可以讓一條邊上的流量為0。舉個(gè)例子，若算法過(guò)程產(chǎn)生了fij=8，fji=3，從節(jié)點(diǎn)i和j之間經(jīng)過(guò)的流量角度，等價(jià)于fij=5，fji=0。

參考文獻(xiàn)：

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

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

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