Ford-Fulkerson 算法教程

Ford-Fulkerson 算法是一种用于解决网络流问题的算法。它通过迭代地增加流，直到没有更多的流可以增加，来找到网络中的最大流。

算法步骤

初始化：设置流 ( f ) 为 0，令 ( s ) 为源点，( t ) 为汇点。
寻找增广路径：使用 BFS 或 DFS 寻找从 ( s ) 到 ( t ) 的增广路径 ( P )。
增加流：对于路径 ( P ) 上的每一条边 ( (u, v) )，计算该边的容量 ( c(u, v) ) 和当前流 ( f(u, v) ) 的差值，取最小值作为当前增广路径的流量 ( \Delta )。然后将 ( \Delta ) 加到 ( f(u, v) ) 上，并将 ( \Delta ) 减去 ( f(v, u) )（因为 ( (v, u) ) 是 ( (u, v) ) 的反向边）。
重复步骤 2 和 3：直到没有更多的增广路径可以找到。

代码示例

以下是一个使用 BFS 寻找增广路径的 Ford-Fulkerson 算法示例：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
    
    def add_edge(self, s, t, w):
        self.graph[s].append((t, w))
        self.graph[t].append((s, 0))
    
    def bfs(self, s, t, parent):
        visited = [False] * self.V
        queue = []
        queue.append(s)
        visited[s] = True
        
        while queue:
            u = queue.pop(0)
            
            for v, cap in self.graph[u]:
                if not visited[v] and cap > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
        
        return visited[t]
    
    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.V
        max_flow = 0
        
        while self.bfs(source, sink, parent):
            path_flow = float('inf')
            s = sink
            
            while s != source:
                u = parent[s]
                path_flow = min(path_flow, self.graph[u][self.graph[u].index((s, 0))][1] - self.graph[u][self.graph[u].index((s, 0))][2])
                s = parent[s]
            
            max_flow += path_flow
            v = sink
            
            while v != source:
                u = parent[v]
                f = self.graph[u][self.graph[u].index((v, 0))][2]
                self.graph[u][self.graph[u].index((v, 0))] = (v, self.graph[u][self.graph[u].index((v, 0))][1] - path_flow)
                self.graph[v][self.graph[v].index((u, 0))] = (u, self.graph[v][self.graph[v].index((u, 0))][1] + path_flow)
                v = parent[v]
        
        return max_flow

# 使用示例
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0
sink = 5
print("最大流为：", g.ford_fulkerson(source, sink))

扩展阅读

更多关于 Ford-Fulkerson 算法的介绍和示例，请参考本站算法教程。

图片