福特-富爾克森演算法

福特-富爾克森方法，又稱福特-富爾克森演算法，是一類計算網路流的最大流的貪心演算法。之所以稱之為“方法”而不是“演算法”，是因為它尋找增廣路徑的方式並不是完全確定的，而是有幾種不同時間複雜度的實現方式。它在1956年由小萊斯特·倫道夫·福特及德爾伯特·雷·富爾克森發表。“福特-富爾克森”這個名詞通常也指代埃德蒙茲-卡普演算法，這是一個特殊的福特-富爾克森演算法實現。演算法的思想如下：只要有一條從源點的路徑，在路徑的所有邊上都有可用容量，就沿著這條路徑傳送一個流，流量由路徑上的最小容量限制。 然後再找到另一條路徑，一直到網路中不存在這種路徑為止。 一條有可用容量的路徑被稱為一條增廣路徑。演算法.設formula_1為一個圖，並且為每條從formula_2到formula_3的邊formula_4設定一個最大流量formula_5，並且初始化當前流量formula_6。下面是該演算法每一步的實現：這意味著每輪計算之後透過網路的都是一個流。我們定義殘留網路 formula_7是一個網路的剩餘流量formula_8。注意殘留網路可以設定從formula_3到formula_2的流量，即使在原先的網路中不允許這種情況產生：如果 formula_11 但 formula_12，那麼formula_13：也即，從formula_2到formula_3的流量給從formula_3到formula_2的流量提供了額外的剩餘量。虛擬碼.演算法 福特-富爾克森輸入 給定一張邊的容量為formula_18的圖formula_19，源點formula_20以及匯點formula_21。輸出 在網路formula_22中，從formula_20到formula_21的最大流formula_25。# 初始化網路流量formula_26、殘留網路formula_27。對於圖的每一條邊formula_4，初始化流量formula_29。# 只要formula_30中還存在一條從formula_20到formula_21的路徑formula_33，使對於每一條邊formula_34，都有formula_35：## 設定路徑formula_33本次應傳送的流量為路徑最小剩餘流量：formula_37。##更新網路流量formula_38。## 對於每一條邊formula_34，更新formula_30的剩餘流量：### formula_41 "### formula_42 "步驟2中的路徑formula_33可以用廣度優先搜尋或深度優先搜尋在formula_7中找到。如果使用了廣度優先搜尋，這個演算法就是Edmonds–Karp演算法。當步驟2中找不到可行路徑時，formula_20就無法在殘留網路中到達formula_21。設formula_47是在殘留網路中formula_20可以到達的節點的集合，然後從formula_47到formula_50的其餘部分的網路一方面等於我們找到的從formula_20到formula_21的所有流的總流量，另一方面所有這樣的流量組成了一個上限。這說明我們找到的流是最大的。大流最小割定理。如果圖formula_1有多個源點和匯點，可以按如下方法處理：設formula_54，formula_55。 新增一個新源點formula_56與所有源點有一條邊formula_57相連，容量formula_58。新增一個新匯點formula_59與所有匯點formula_60 有一條邊相連，容量formula_61。然後執行福特-富爾克森演算法。同樣的，如果節點formula_2有透過限制formula_63，可將這個節點用兩個節點formula_64替換，用一條邊formula_65相連，容量為formula_66。然後執行福特-富爾克森演算法。複雜度.演算法透過新增找到的增廣路徑的流量增加總流量，當無法找到增廣路徑時，總流量就達到了最大。當流量是整數時，福特-富爾克森演算法的執行時間為formula_67, formula_68圖中的邊數，formula_25為最大流。 這是因為一條增廣路徑可以在formula_70的時間複雜度內找到，每輪演算法執行後流量的增長至少為formula_71。但是在極端情況下，演算法有可能永遠不會停止。福特-富爾克森演算法的一個特例是埃德蒙茲-卡普演算法，時間複雜度為formula_72。樣例.下面的樣例演示了福特-富爾克森在一張有4個節點，源點為formula_73，匯點為formula_74的圖中的第一輪計算。 這個例子顯示了演算法在最壞情況下的行為。在每一輪演算法中，只有formula_71的流量被髮送至網路中。如果演算法改用寬度優先搜尋，那麼只需要兩輪計算。注意當找到路徑formula_76時，流是如何從formula_77傳送至formula_78的。無法終止演算法的樣例.右圖所示的網路中源點為formula_20，匯點為formula_21邊formula_81、formula_82、formula_83的容量為formula_71, formula_85和formula_71，使formula_87。其它所有邊的容量formula_88。 使用福特-富爾克森演算法可找到三條增廣路徑，分別為formula_89、formula_90、formula_91.注意在步驟1和步驟5之後,邊formula_81、formula_82、formula_83的殘留容量都可以表示為formula_95、formula_96或formula_97，同時，對於一些特殊的formula_98這意味著演算法可以透過formula_99、formula_100、formula_99與 formula_102無限增廣，並且殘留容量總處於一個迴圈。在步驟5之後網路的流為formula_103，如果繼續用以上的演算法增廣，總的流將向formula_104趨近，但最大流為formula_105。在這個樣例中，演算法將永遠不會停止，且結果也不會向實際的最大流趨近。Python原始碼.class Edge(object):def __init__(self, u, v, w):self.source = uself.sink = vself.capacity = wdef __repr__(self):return "%s-&gt;%s:%s" % (self.source, self.sink, self.capacity)class FlowNetwork(object):def __init__(self):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 = redgeredge.redge = edgeself.adj[u].append(edge)self.adj[v].append(redge)self.flow[edge] = 0self.flow[redge] = 0def find_path(self, source, sink, path):if source == sink:return pathfor edge in self.get_edges(source):residual = edge.capacity - self.flow[edge]if residual &gt; 0 and edge not in path:result = self.find_path( edge.sink, sink, path + [edge])if result != None:return resultdef 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] += flowself.flow[edge.redge] -= flowpath = self.find_path(source, sink, [])return sum(self.flow[edge] for edge in self.get_edges(source))使用樣例.»&gt; g = FlowNetwork()»&gt; [g.add_vertex(v) for v in "sopqrt"][None, None, None, None, None, None]»&gt; g.add_edge('s','o',3)»&gt; g.add_edge('s','p',3)»&gt; g.add_edge('o','p',2)»&gt; g.add_edge('o','q',3)»&gt; g.add_edge('p','r',2)»&gt; g.add_edge('r','t',3)»&gt; g.add_edge('q','r',4)»&gt; g.add_edge('q','t',2)»&gt; print (g.max_flow('s','t'))5應用.二分圖的最大匹配最大不相交路徑