網絡流（最大流問題）

前序

在將網絡里實現算法之前，我們得聊聊網絡流究竟是個什么東西，畢竟只有知道它的樣貌，才能繼續看懂下面的定義，對吧？

---

首先，網絡流不僅僅指的是什么FF算法、dinic算法。算法只是用來解決問題的（稍后我們會更加能體會這一點），而網絡流，指的就是這一系列存在圖論中的，關于“流（Flow）”的問題。

參考：Network flow problem - Wikipedia

網絡流中有以下幾種問題：

• 最大流問題
• 最小費用流問題
• 多商品流問題(multi-commodity flow problem)
• 非零流問題(Nowhere-zero flow)

本文著重于最大流問題，闡述其問題和算法的過程和個人理解，方便其他人學習。

文章目的

個人某天刷leetcode的時候遇到了網絡流算法。于是為了擴展知識面我便到處找關于網絡流算法的文章和視頻去看，但是無論是OIer的視頻還是其他CSDN的文章都不免省略了很多……呃，也不是說是細節，而是更多的關于算法本身理解的部分，尤其是在所有人都對反向邊的建立解釋為“反悔”一詞，大家的理解如此一致使得初學者很難去好好的理解算法本身。

這就好像老師強行要求學生按照某一既定方式去理解世界一樣，不是說老師的方法是錯誤的，而是——有些人其實思維方式很可能和老師不同，這樣它就很難按照老師的思路去學習。

所以本文的目的就是——不說是發明吧，盡量用一些方法對最大流問題以及其算法本身有著更多的解釋（理解），方便后來人能夠全面的學習。

那么，我們就開始吧。

最大流問題

對于問題最好的理解就是問題本身。

查一下百度就能知道，一個名字叫T.E.哈里森的人在1955年提出了鐵路網絡中兩點間最大運輸量的問題。不僅如此，這貨為此還發了一個60余頁的論文，從此成為了折磨后人的罪魁禍首。

我找到了他的論文，看看他究竟為什么想出這個破問題的。

原文：https://ntlrepository.blob.core.windows.net/lib/13000/13200/13238/AD093458.pdf

---

ps：個人實在是沒有太多的精力去研究論文本身，而且論文似乎設計了一些鐵路相關的背景知識，所以我并不打算講解。此處引用文章只是為了追溯問題本身，了解一些背景知識。

---

論文一開始哈里森就指出了這篇論文的目的(Purpose of this paper)。大致的意思就是，論文的目的并不是為了讓使用計算機的新手也能代替一些能夠預測鐵路運輸量的專家，相反，專家就應該去做專家的事情。

哈里森說，當前（1954年）的鐵路專家都是依靠經驗去做事，很少和數字打交道（應該指的是很多專家沒有數學建模的能力）。所以他們得出的結論往往含有很多的人為因素?！霸趯＜覀冏龀鲇行У墓罍y之前，長時間的艱苦研究和計算是必不可少的”，哈里森說。

但另一方面，在面對無數問題甚至規劃戰役的時候，他們往往急需計劃的結果，無法等待專家們去計算其中的細節。

因此，提供一種幫助專家快速、準確的預估方法將會有很大幫助。

這就是最大流問題的來源，甚至可以說這是所有算法的來源。在實際問題中抽象出數學，然后使用數學的方法解決數學的問題。

算法的根本目的就在于此，甚至數學的目的也是這樣。

我們聽到了太多關于知識本身的質疑，即便是我，也曾思考過數學的用途，甚至是他的意義。

結論其實非常簡單——用數學（算法）抽象，然后用數學（算法）解決，最后用數學（算法）套用。

數學（算法）成為了問題和解決方案之間的橋梁，我們深入算法，就是深入問題本身。

---

最大流求解

基本定義

• 有向網絡

  首先，我們要做的就是將實際問題抽象。以上面鐵軌網絡為例子，如何抽象火車網絡成為一種數學模型？

  噢，即便你沒有學過圖論，憑借直覺你也能想到。車站可以作為點，鐵軌作為線，然后用線把點連起來，這樣不就是表示出火車網絡了嗎？

  是的，你想沒錯。不過你還可以想的更深——火車的行駛當然有方向，尤其是在我們想要求解特定兩點之間的情況下，所以作為鐵軌的線應該改成向量。

  OK了，這樣我們就完成了初步建模，離最終數學的答案更近了一部。

  恭喜你，建立了一個有向圖

• 容量

  唔……好像還差一些東西。網絡有了，流呢？不要著急，我們在建立流的概念之前還有一些東西需要確定下來。

  每列火車都有承載量，理所應當的，剛剛建立的有向圖中每個向量也應當有一個容量值，限制了這條邊所能運輸的最大貨量。

• 流

  你可能會想流是怎樣的定義的？其實關于流的定義大家感受一下就好，甚至直接按照字面意義理解也不為過。電流的流、河流的流、最大流的流，都差不多。

  不過我還是貼出流在wikipedia中的定義：
  

  一個流是一個滿足以下要求的映射 f : E -> R

  • 容量限制：每條邊的流≤該邊的容量。
  • 流守恒：流入一個節點的流總和=流出該節點的流的總和

  流量代表著從源點流入匯點的流的數量

嗯……讓我想想還差什么東西……對了！

怎么能少了真正的圖呢，這才是最重要的，一張圖就可以代表所有的定義，很簡單，也直觀，對吧？

人工解決

趁著圖還在上面，我們人工算一下這個網絡中的最大流。

我們把源點、匯點和邊的代號給編輯一下。

從S匯出的流能走幾條路？

• a-d
• b-c-d
• b-e-f

三條，這三條路中的流量是多少？

• a-d：8，因為a是8限制了流
• b-c-d：3，但是除了因為c限制了3的流量之外，還有另一件事需要注意。因為a-d這條路占用了d中的8個容量，所以在進行b-c-d計算的時候要記住，3的由來是min(10,3,4).
• b-e-f：3，因為min(7,3,5)

于是，總的流量加起來是8+3+3 = 14

看起來還是挺好弄得嗎，似乎只要遍歷每條路，然后便利的時候每條邊取最小值然后減去最小值就行了。

OK，換了例子。例子取自電子科技大學的視頻

我先求得該圖得最大流

• a-d-g：3
• a-e-h：2
• b-f-g：1 = min(6,4,1)
• b-c-h：4 = min(5,4,6)

最大流為10。

接下來我們將引出計算機得缺陷了——他不懂順序得重要性。我們首先遍歷從a邊出去的流，得到的答案沒什么問題，但是計算機不知道，我們完全無法得知他會先計算那條邊，假設我們先從b邊開始

• b-f-g：4
• b-c-h：2 = min(2,4,8)
• a-d-g：0 = min(7,3,0)
• a-e-h：2 = min(7,2,6)

最終，我們得出圖的最大流為8。

這就是計算機的問題所在，我們需要招到一種方法（算法），讓計算機能夠不在乎先后完美的計算出正確的答案。

問題分析

我們不妨分析分析為什么順序會影響結果。

當我們率先計算b-f-g這條邊的時候，我們貪心的把整條路都填滿，導致g的容量全部被來自b的量占據了。這代表著a無法再利用這條邊，只能向下從e流出。

甚至我們可以想象，在復雜的網絡中，一個節點的流出的邊很可能全部被其他流占用，導致流向該節點的“貨物”全部失效了。如果這部分貨物占據了總流量的很大部分，那么結果就很有可能出現錯誤。

為了避免這個現象Ford-Fulkerson算法建立了反向邊，即“反悔”機制。

它，是這樣做的。

算法沿著路徑反向建立額外的路，這條額外的路的容量就等于整條路的流量。

此時，我們完成了第一步，即b-f-g：4

然后我們繼續

• b-c-h：2
• a-d-f’-c-h：2
• a-e-h：2

最大流4+2+2+2=10。結果正確。

在這里你能看到“反悔”機制是如何作用的，他將多余的流量回退。本來正確的路線是b-f-g：1，結果我們因為順序的不同導致b-f-g率先占據更多的容量，而反向邊的建立使得我們有機會將多余的3份流量回退回去，產生正確的結果。

到這里其實你已經能懂個大概了，甚至也許你不要更精進一步，對于FF算法最核心部分的反向邊建立的必要性已經得知了之后你便可以直接去看算法源碼，然后再著基礎上去看EK算法以及Dinic算法，接下想必對于你來說只是時間問題了。

---

額外內容

真的反悔了嗎？

而我接下來要反駁一下“反悔”這個理解（注意，我并非反對這個機制，而是“反悔”這個詞的用法。）

請看下面的例子：

按照FF算法求最大流是12。

FF算法是一種貪心算法，它總是盡可能沾滿一條邊的容量。比如從a-c這條路走，它會送出去5的流量，而非3或4。這個概念其實相當重要。

正確計算順序是這樣的：

• a-c：5
• a-e-d：5
• b-d：2

但順序打亂一下，同時建立反向邊：

• a-e-d：8
• a-c：2
• b-e’-c：2

結果正確，但是這個時候我們再以“反悔”的視角來看，按照剛才的順序，a-e-d這條路應該是5，應該反悔3個流才能得到正確的答案，但是這里我們僅僅反悔了兩個流，也就是說，現在成了這個樣子：

• a-e-d：8-2=6
• a-c：2+2=4
• b-d：0+2=2

a的分配明顯不符合貪心的思想。

但關鍵就在于這一點，即便不符合貪心，即便沒有完全的“反悔”，算法依舊健壯，依舊完美的運作，其中所蘊含的數學究竟是什么？是什么保證了它如此完美的運作？

接下來，才是我想討論的重點。

---

不是“反悔”，是“借用”

接下來我們將進行一系列的分類討論，可能會有點繞，有點暈，所以我盡量講的清晰一點。

為了使例子更具有普遍性，我們講每條邊的容量值用任意值代替。

好吧，我的字母好像兩條邊標反了，不過不用在意，都是一樣的。

a先走c：這個時候我們先讓a優先占用c邊，有兩種情況。

• a<c：這個時候不需要建立反向邊，因為a不走e，a的流量全部被c給拿走了。
• a>c：當a大于c時，那么a剩余的流量會走e同時建立反向邊。但是這個時候反向邊也是無用的，試想，當b流通過反向邊來到c時，發現c的容量早已經被a占滿了。所以反向邊的建立起不到任何作用，b還是老老實實走d才行。

可以看到，a先走c是符合我們計算順序的，這個時候無論建不建立反向邊都是不影響結果的。

a先走e：兩種情況

• a<e：這個時候建立反向邊，但是往下b和e匯合的時候還分兩種情況
  • b+e<d：這說明d容量足夠大，足以容納a和b的總容量，b這個時候也有可能不走反向邊。
    • 如果b不走反向邊，正常運作
    • 如果b走反向邊，那么b就會和反向邊的容量判斷大小，之后剩余容量肯定能走d，通過反向邊的流量則借用原來a需要走的c邊。
  • b+e>d：這個時候b的剩余容量就必須要走反向邊，借用a原來走的c邊。
• a>e：如果a有剩余流量，它會講剩余流量走c邊，同時建立反向邊讓b邊有機會借用c自己的c邊，防止b被阻塞。

好吧，我承認上述的分類有些亂糟糟的，確實這方面也不太好說，所以我下面以一種方便的形式展示一下 “借用” 的意思。

---

當a流來到中間上面的節點的時候，它會發現有兩條路，分別是e和c。而a最討厭選擇了，因為選擇意味著你需要照顧其他路的情況。

a完全不知道它流向的路是否被其他流共享，比如說當a流流向e-d的時候，它完全不知道c的存在，也不知道自己的流量會不會阻塞c。

a是個自私的人，它選擇時候不在乎別人的想法，但a是個聰明的人。

當a選擇自己的x份流量流向某一路的時候，那么a知道自己其他路的流量就會減少x份。

a表示：“我自己不想管其他人，反正我這里隨便分配自己的流量，別人要是因為我的流量被堵住了，那他們來借用我減少流量的路好了。”

以上面的例子來說，就是這個例子

當a先走e的時候，他知道自己c路將缺少流量，于是它決定建立反向的橋梁讓其他路能夠沿著這條路取借用自己的c邊。

于是b再遍歷的時候發現自己的d邊被a占用了，雖然它很不爽，但是它只能沿著a架起的橋梁取走c的邊。

事實上，當a走d的時候它也在借用d的容量，借用的數量取決于這條路上容量的最小值。

a說：“抱歉我用了你們的路，但是相反你們也能借用我的路，但是你們借用的不能超過我借用的！”

也就是a再建立反向邊的同時設定反向邊的容量等于該路的流量。

在上面的圖中，雖然b的流量不足以填滿a借用的，但是假如我再下面中間節點的底下再連上一條流，這條流也會借用反向邊走b，一直到把a的借債填滿為止。

這就是我自己對于最大流反向邊建立算法的理解。

a在決定流的流入方向的同時，還不想阻塞其他流，所以它建立反向邊允許其他流借用自己的邊。這樣，互相借用達成一種平衡，就是算法正確性的保證。

---

FF算法

FF算法就好像我們上面的人工過程，找到一個節點，從這個節點開始貪心填滿與他相連的每一條邊，用dfs同時建立反向邊給予其他節點借用的機會，然后一點點算下去就行了。

wikipedia上面有python的代碼，而且如果你自己想找代碼的話我相信你也能找到合適的。

我這里貼上Wiki的代碼

import collectionsclass Graph:"""This class represents a directed graph using adjacency matrix representation."""def __init__(self, graph):self.graph = graph # residual graphself.row = len(graph)def bfs(self, s, t, parent):"""Returns true if there is a path from source 's' to sink 't' inresidual graph. Also fills parent[] to store the path."""# Mark all the vertices as not visitedvisited = [False] * self.row# Create a queue for BFSqueue = collections.deque()# Mark the source node as visited and enqueue itqueue.append(s)visited[s] = True# Standard BFS loopwhile queue:u = queue.popleft()# Get all adjacent vertices of the dequeued vertex u# If an adjacent has not been visited, then mark it# visited and enqueue itfor ind, val in enumerate(self.graph[u]):if (visited[ind] == False) and (val > 0):queue.append(ind)visited[ind] = Trueparent[ind] = u# If we reached sink in BFS starting from source, then return# true, else falsereturn visited[t]# Returns the maximum flow from s to t in the given graphdef edmonds_karp(self, source, sink):# This array is filled by BFS and to store pathparent = [-1] * self.rowmax_flow = 0 # There is no flow initially# Augment the flow while there is path from source to sinkwhile self.bfs(source, sink, parent):# Find minimum residual capacity of the edges along the# path filled by BFS. Or we can say find the maximum flow# through the path found.path_flow = float("Inf")s = sinkwhile s != source:path_flow = min(path_flow, self.graph[parent[s]][s])s = parent[s]# Add path flow to overall flowmax_flow += path_flow# update residual capacities of the edges and reverse edges# along the pathv = sinkwhile v != source:u = parent[v]self.graph[u][v] -= path_flowself.graph[v][u] += path_flowv = parent[v]return max_flow

Dinic算法

之后的算法都是改進，如何才能更有效的算出結果。

Dinic算法在dfs基礎上使用bfs將節點分層，分層后的節點保證算法不會兜圈子走遠路。

Dinic算法會使用BFS不斷更新節點的層數，便利的時候保證流向層次高的節點，而不是通過同層次的節點。

我很推薦大家去看Dinic算法的wikipedia，他下面有還算清晰的過程展示，至少比大多數文章要好。

如果你登不上wiki……

請看第一次bfs和dfs，主要到有些邊算法目前還沒有走，因為那些點處在同層次上，算法要求dfs必須走下一層次的節點。

有些邊已經完全占滿了，所以可以刪掉他們了。

上一層中1->2的路6/8雖然有剩余，但是已經完全無法利用了，在bfs時候將他作為第3層次節點，而且該層次節點不能流入到t節點，它是無效的。

將上面的圖占滿的邊刪掉，bfs的時候只能走到1的那個節點了。

這個過程中你依舊能看到反向邊的建立，但是似乎沒怎么利用就是了。

---

至于Dinic算法的優化，如果你看一個算法首先先搞清處它優化在什么地方，那就本末倒置了。

順便，如果你看不懂head數組和edge數組，去看圖的鏈式前向星表示方法。

然后，每個節點都可能連著多個邊，有些邊連著下一層次的節點，他會在dfs中遍歷到然后找到增廣路，于是這條路之后就不需要再次遍歷了，我們不斷更新head數組中第一條邊的位置就能實現弧優化了。

至于多路增廣，我總感覺跟dfs差不多？這我還沒完全看出來。

不過，太過注重優化有有些走偏了，算法——還是用來解決問題的呀。

---

總結

以上是生活随笔為你收集整理的全面理解网络流中的最大流问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。