DSA Ford-Fulkerson 演算法

Ford-Fulkerson 演算法

Ford-Fulkerson 演算法用於求解有向圖的最大流問題。

流從源頂點 (\(s\)) 發出，到達匯頂點 (\(t\))，並且圖中的每條邊都有一個由容量限制的流量。

Ford-Fulkerson 演算法透過尋找一條具有可用容量從源到匯的路徑（稱為增廣路徑），然後透過該路徑傳送儘可能多的流量來工作。

Ford-Fulkerson 演算法會持續尋找新的路徑來發送更多流量，直到達到最大流。

在上面的模擬中，Ford-Fulkerson 演算法解決了最大流問題：它計算了可以從源頂點 \(s\) 傳送到匯頂點 \(t\) 的最大流量，最大流量為 8。

上面模擬中的數字以分數形式顯示，第一個數字是流量，第二個數字是容量（該邊可能的最大流量）。例如，邊 \(s \rightarrow v_2\) 上的 0/7 表示有 0 的流量，容量為 7。

下面是 Ford-Fulkerson 演算法工作原理的基本分步描述，但我們需要稍後進行更詳細的講解才能真正理解它。

Ford-Fulkerson 中的殘餘網路

Ford-Fulkerson 演算法實際上是透過建立和使用稱為殘餘網路的內容來工作的，它代表了原始圖。

在殘餘網路中，每條邊都有一個殘餘容量，它等於邊的原始容量減去該邊的流量。殘餘容量可以被視為具有一定流量的邊的剩餘容量。

例如，如果邊 \( v_3 \rightarrow v_4 \) 的流量為 2，而容量為 3，則該邊的殘餘流量為 1，因為透過該邊還可以傳送 1 個單位的流量。

Ford-Fulkerson 中的反向邊

Ford-Fulkerson 演算法還使用一種稱為反向邊的機制來反向傳送流量。這對於增加總流量很有用。

例如，上面動畫中以及下面手動演示中的最後一條增廣路徑 \(s \rightarrow v_2 \rightarrow v_4 \rightarrow v_3 \rightarrow t\) 表明，透過實際上在邊 \( v_4 \rightarrow v_3 \) 上反向傳送流量，總流量增加了 1 個單位。

在我們示例中，在邊 \( v_3 \rightarrow v_4 \) 上反向傳送流量意味著，流出頂點 \( v_3 \) 的這個 1 個單位的流量，現在從邊 \( v_3 \rightarrow t \) 離開 \( v_3 \)，而不是從 \( v_3 \rightarrow v_4 \)。

要反向傳送流量，與原始邊方向相反，為網路中的每條原始邊都建立一個反向邊。然後，Ford-Fulkerson 演算法就可以使用這些反向邊來反向傳送流量。

反向邊沒有流量或容量，只有殘餘容量。反向邊的殘餘容量總是與相應原始邊的流量相同。在我們的示例中，邊 \( v_3 \rightarrow v_4 \) 的流量為 2，這意味著相應的反向邊 \( v_4 \rightarrow v_3 \) 的殘餘容量為 2。

這僅僅意味著，當原始邊 \( v_3 \rightarrow v_4 \) 的流量為 2 時，就可以以相反的方向將相同數量的流量透過該邊反向傳送。使用反向邊推回流量也可以被視為撤銷已建立的部分流量。

殘餘網路的概念（具有邊上的殘餘容量）以及反向邊的概念是 Ford-Fulkerson 演算法工作原理的核心，我們將在頁面下方實現該演算法時詳細介紹。

手動演練

最初，圖中沒有流量。

為了找到最大流，Ford-Fulkerson 演算法必須增加流量，但首先需要弄清楚流量可以在哪裡增加：它必須找到一條增廣路徑。

Ford-Fulkerson 演算法實際上沒有規定如何找到這樣的增廣路徑（這就是為什麼它經常被描述為一種方法而不是演算法），但在本教程中，我們將使用深度優先搜尋 (DFS) 來為 Ford-Fulkerson 演算法找到增廣路徑。

Ford-Fulkerson 使用 DFS 找到的第一條增廣路徑是 \(s \rightarrow v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow t\)。

透過瓶頸計算，Ford-Fulkerson 發現可以透過增廣路徑傳送的最高流量是 3，因此該路徑中所有邊的流量都增加了 3。

Ford-Fulkerson 演算法的下一次迭代是再次執行這些步驟

2. 找到新的增廣路徑
3. 找出該路徑中的流量可以增加多少
4. 相應地增加該路徑中邊的流量

下一條增廣路徑被發現是 \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow v_3 \rightarrow t\)，它包括反向邊 \(v_4 \rightarrow v_3\)，其中流量被反向傳送。

Ford-Fulkerson 的反向邊概念非常有用，因為它允許演算法的路徑查詢部分找到一條可以包含反向邊的增廣路徑。

在這種特定情況下，這意味著可以透過邊 \(v_3 \rightarrow v_4\) 反向傳送 2 個單位的流量，並將其傳送到 \(v_3 \rightarrow t\)。

由於 \( v_3 \rightarrow t \) 邊的容量限制，該路徑的流量只能增加 2。

下一條增廣路徑被發現是 \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\)。

該路徑中的流量可以增加 2。瓶頸（限制邊）是 \( v_1 \rightarrow v_4 \)，因為該邊只剩下傳送兩個單位流量的空間。

下一條也是最後一條增廣路徑是 \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\)。

由於邊 \( v_4 \rightarrow t \) 是此路徑中的瓶頸，僅剩一個單位流量的空間（\(capacity-flow=1\)），因此此路徑的流量只能增加 1。

此時，無法再找到新的增廣路徑（即找不到可以從 \(s\) 到 \(t\) 傳送更多流量的路徑），這意味著已找到最大流，Ford-Fulkerson 演算法完成。

最大流量為 8。如您在上面的圖片中看到的，源頂點 \(s\) 流出的流量（8）與匯頂點 \(t\) 流入的流量相同。

此外，如果您取除了 \(s\) 或 \(t\) 以外的任何其他頂點，您會發現流入該頂點的流量等於流出該頂點的流量。這就是我們所說的流量守恆，對於所有此類流網路（每條邊都有流量和容量的有向圖），都必須滿足此條件。

Ford-Fulkerson 演算法的實現

為了實現 Ford-Fulkerson 演算法，我們建立一個 Graph 類。 Graph 類表示具有頂點和邊的圖。

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

第 3 行：我們建立 adj_matrix 來儲存所有邊和邊容量。初始值設定為 0。

第 4 行：size 是圖中頂點的數量。

第 5 行：vertex_data 儲存所有頂點的名稱。

第 7-8 行： add_edge 方法用於新增一條從頂點 u 到頂點 v 的邊，容量為 c。

第 10-12 行： add_vertex_data 方法用於向圖中新增頂點名稱。vertex 引數給出頂點的索引，data 是頂點的名稱。

Graph 類還包含 dfs 方法，用於透過深度優先搜尋查詢增廣路徑。

    def dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

        visited[s] = True
        path.append(s)

        if s == t:
            return path

        for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

        return None

第 15-18 行： visited 陣列有助於避免在搜尋增廣路徑時重複訪問相同的頂點。屬於增廣路徑的頂點儲存在 path 陣列中。

第 20-21 行：當前頂點被標記為已訪問，然後新增到路徑中。

第 23-24 行：如果當前頂點是匯節點，則已找到從源頂點到匯頂點的增廣路徑，因此可以返回該路徑。

第 26-30 行：迴圈遍歷鄰接矩陣中的所有邊，從當前頂點 s 開始。ind 表示相鄰節點，val 是到該頂點的邊的殘餘容量。如果相鄰頂點未被訪問，並且到該頂點的邊有殘餘容量，則轉到該節點並繼續從該頂點搜尋路徑。

第 32 行：如果找不到路徑，則返回 None。

我們新增到 Graph 類中的最後一個方法是 fordFulkerson 方法。

    def fordFulkerson(self, source, sink):
        max_flow = 0

        path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

            max_flow += path_flow

            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

            path = self.dfs(source, sink)

        return max_flow

最初，max_flow 為 0，並且 while 迴圈只要存在可以增加流量的增廣路徑，就會繼續增加 max_flow。

第 37 行：找到增廣路徑。

第 39-42 行：檢查增廣路徑中的每條邊，以確定可以透過該路徑傳送多少流量。

第 44-46 行：由於流量增加，每個正向邊的殘餘容量（容量減去流量）都會減少。

第 47 行：這代表了反向邊，Ford-Fulkerson 演算法使用它來允許流量被反向傳送（撤銷）原始正向邊。重要的是要理解，這些反向邊不在原始圖中，它們是 Ford-Fulkerson 引入的虛構邊，以使演算法能夠工作。

第 49 行：每次透過增廣路徑增加流量時，max_flow 都會增加相同的值。

第 51-52 行：這只是為了在演算法開始下一個迭代之前列印增廣路徑。

定義完 Graph 類後，必須定義頂點和邊來初始化特定圖，Ford-Fulkerson 演算法示例的完整程式碼如下所示。

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

        visited[s] = True
        path.append(s)

        if s == t:
            return path

        for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

        return None

    def fordFulkerson(self, source, sink):
        max_flow = 0

        path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

            max_flow += path_flow

            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

            path = self.dfs(source, sink)

        return max_flow

g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
    g.add_vertex_data(i, name)

g.add_edge(0, 1, 3)  # s  -> v1, cap: 3
g.add_edge(0, 2, 7)  # s  -> v2, cap: 7
g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3
g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4
g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5
g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3
g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3
g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2
g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6

source = 0; sink = 5

print("The maximum possible flow is %d " % g.fordFulkerson(source, sink))

Ford-Fulkerson 演算法的時間複雜度

Ford-Fulkerson 的時間複雜度因頂點數 \(V\)、邊數 \(E\) 以及實際上圖中的最大流 \(f\) 而異。

時間複雜度之所以會隨圖中最大流 \(f\) 而變化，是因為在吞吐量很大的圖中，會有更多的增廣路徑來增加流量，這意味著查詢這些增廣路徑的 DFS 方法需要執行更多次。

深度優先搜尋 (DFS) 的時間複雜度為 \(O(V+E)\)。

DFS 每次執行一次，代表一條新的增廣路徑。如果我們假設每條增廣圖都增加 1 個單位的流量，DFS 就必須執行 \(f\) 次，即最大流量值次數。

這意味著，使用 DFS 的 Ford-Fulkerson 演算法的時間複雜度為

\[ O( (V+E) \cdot f ) \]

對於稠密圖，其中 \( E > V \)，DFS 的時間複雜度可以簡化為 \(O(E)\)，這意味著 Ford-Fulkerson 演算法的時間複雜度也可以簡化為

\[ O( E \cdot f ) \]

稠密圖沒有精確的定義，但它是一種邊很多的圖。

我們將描述的下一個查詢最大流的演算法是Edmonds-Karp 演算法。

Edmonds-Karp 演算法與 Ford-Fulkerson 非常相似，但它使用 BFS 而不是 DFS 來查詢增廣路徑，從而減少了查詢最大流的迭代次數。