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 \) 上发送反向流量来增加总流量一个单位，从而将流量发送到反方向。

在我们这个例子中，在边 \( v_3 \rightarrow v_4 \) 上反向发送流量意味着这 1 个单位从顶点 \( v_3 \) 出发的流量，现在在边 \( 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 关于逆边的概念非常有用，因为它允许算法的路径查找部分找到包含逆边的增广路径。

在這種特定情況下，意味著可以將 2 的流量回傳到邊緣 \(v_3 \rightarrow v_4\)，轉而進入 \(v_3 \rightarrow t\)。

此路徑的流量只能增加 2，因為這是 \( v_3 \rightarrow t \) 邊緣的容量。

下一個增廣路徑被發現是 \(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\)。

此路徑的流量只能增加 1，因為邊緣 \( v_4 \rightarrow t \) 是此路徑的瓶頸，而且只有容納一個額外流量單位的空間（\(容量-流量=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。

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

    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 來尋找增廣路徑，這導致找到最大流量的迭代次數減少。