福特-富爾克森算法

福特-富爾克森方法(英語:Ford–Fulkerson method),又稱福特-富爾克森算法Ford–Fulkerson algorithm),是一類計算網絡流最大流貪心算法。之所以稱之為「方法」而不是「算法」,是因為它尋找增廣路徑的方式並不是完全確定的,而是有幾種不同時間複雜度的實現方式[1][2]。它在1956年由小萊斯特·倫道夫·福特德爾伯特·雷·富爾克森[3]發表。「福特-富爾克森」這個名詞通常也指代埃德蒙茲-卡普算法,這是一個特殊的福特-富爾克森算法實現。

算法的思想如下:只要有一條從源點(開始節點)到匯點(結束節點)的路徑,在路徑的所有邊上都有可用容量,就沿着這條路徑發送一個流,流量由路徑上的最小容量限制。 然後再找到另一條路徑,一直到網絡中不存在這種路徑為止。 一條有可用容量的路徑被稱為一條增廣路徑。

算法

 為一個圖,並且為每條從  的邊 設置一個最大流量 ,並且初始化當前流量 。下面是該算法每一步的實現:

容量限制:   每條邊上的流都不能超出邊的最大流量。
反向對稱:     的流量一定是從  的流量的相反數(見樣例)。
流量守恆:   除非 是源點 或匯點 ,一個節點的淨流量為零。
f的值:   從源點 流出的流量一定等於匯點 接收的流量。

這意味着每輪計算之後通過網絡的都是一個流。我們定義殘留網絡  是一個網絡的剩餘流量 。注意殘留網絡可以設置從  的流量,即使在原先的網絡中不允許這種情況產生:如果   ,那麼 :也即,從  的流量給從  的流量提供了額外的剩餘量。

偽代碼

算法 福特-富爾克森

輸入 給定一張邊的容量為 的圖 ,源點 以及匯點 
輸出 在網絡 中,從  的最大流 
  1. 初始化網絡流量 、殘留網絡 。對於圖的每一條邊 ,初始化流量 
  2. 只要 中還存在一條從  的路徑 ,使對於每一條邊 ,都有 
    1. 設置路徑 本次應發送的流量為路徑最小剩餘流量: 
    2. 更新網絡流量 
    3. 對於每一條邊 ,更新 的剩餘流量:
      1.  在路徑中「發送」流)
      2.  這個流在之後可以被「發送」回來)

步驟2中的路徑 可以用廣度優先搜索深度優先搜索 中找到。如果使用了廣度優先搜索,這個算法就是Edmonds–Karp算法

當步驟2中找不到可行路徑時, 就無法在殘留網絡中到達 。設 是在殘留網絡中 可以到達的節點的集合,然後從  的其餘部分的網絡一方面等於我們找到的從  的所有流的總流量,另一方面所有這樣的流量組成了一個上限。這說明我們找到的流是最大的。參見最大流最小割定理

如果圖 有多個源點和匯點,可以按如下方法處理:設  。 添加一個新源點 與所有源點有一條邊 相連,容量 。添加一個新匯點 與所有匯點  有一條邊相連,容量 。然後執行福特-富爾克森算法。

同樣的,如果節點 有通過限制 ,可將這個節點用兩個節點 替換,用一條邊 相連,容量為 。然後執行福特-富爾克森算法。

複雜度

算法通過添加找到的增廣路徑的流量增加總流量,當無法找到增廣路徑時,總流量就達到了最大。當流量是整數時,福特-富爾克森算法的運行時間為 (參見大O符號),  圖中的邊數, 為最大流。 這是因為一條增廣路徑可以在 的時間複雜度內找到,每輪算法執行後流量的增長至少為 。但是在極端情況下,算法有可能永遠不會停止。

福特-富爾克森算法的一個特例是埃德蒙茲-卡普算法,時間複雜度為 

樣例

下面的樣例演示了福特-富爾克森在一張有4個節點,源點為 ,匯點為 的圖中的第一輪計算。 這個例子顯示了算法在最壞情況下的行為。在每一輪算法中,只有 的流量被發送至網絡中。如果算法改用寬度優先搜索,那麼只需要兩輪計算。

路徑 容量 網絡
原流  
     
     
1998輪之後…
最終流  

注意當找到路徑 時,流是如何從 發送至 的。

無法終止算法的樣例

 

右圖所示的網絡中源點為 ,匯點為    的容量為 ,   ,使 。其它所有邊的容量 。 使用福特-富爾克森算法可找到三條增廣路徑,分別為   .

步驟 增廣路徑 發送流 剩餘容量
     
0      
1          
2          
3          
4          
5          

注意在步驟1和步驟5之後,邊   的殘留容量都可以表示為   ,同時,對於一些特殊的 這意味着算法可以通過    無限增廣,並且殘留容量總處於一個循環。在步驟5之後網絡的流為 ,如果繼續用以上的算法增廣,總的流將向 趨近,但最大流為 。在這個樣例中,算法將永遠不會停止,且結果也不會向實際的最大流趨近。[4]

Python源碼

class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v  
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)

class FlowNetwork(object):
    def __init__(self):
        self.adj = {}
        self.flow = {}
 
    def add_vertex(self, vertex):
        self.adj[vertex] = []
 
    def get_edges(self, v):
        return self.adj[v]
 
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0
 
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and edge not in path:
                result = self.find_path( edge.sink, sink, path + [edge]) 
                if result != None:
                    return result
 
    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            residuals = [edge.capacity - self.flow[edge] for edge in path]
            flow = min(residuals)
            for edge in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source))

使用樣例

>>> g = FlowNetwork()
>>> [g.add_vertex(v) for v in "sopqrt"]
[None, None, None, None, None, None]
>>>
>>> g.add_edge('s','o',3)
>>> g.add_edge('s','p',3)
>>> g.add_edge('o','p',2)
>>> g.add_edge('o','q',3)
>>> g.add_edge('p','r',2)
>>> g.add_edge('r','t',3)
>>> g.add_edge('q','r',4)
>>> g.add_edge('q','t',2)
>>> print (g.max_flow('s','t'))
5

應用

二分圖的最大匹配

最大不相交路徑

參考文獻

  1. ^ Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng. Electronic Design Automation: Synthesis, Verification, and Test. Morgan Kaufmann. 2009: 204. ISBN 0080922007. 
  2. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms. MIT Press. 2009: 714. ISBN 0262258102. 
  3. ^ Ford, L. R.; Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8: 399. doi:10.4153/CJM-1956-045-5. 
  4. ^ Zwick, Uri. The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate. Theoretical Computer Science. 21 August 1995, 148 (1): 165–170. doi:10.1016/0304-3975(95)00022-O.