编辑“︁Ford-Fulkerson算法”︁（章节）

== 算法步骤 ==

Ford-Fulkerson算法的伪代码如下：
<syntaxhighlight lang="python">
def ford_fulkerson(graph, source, sink):
    # 初始化流量为0
    max_flow = 0
    # 构建残量网络
    residual_graph = {u: {v: graph[u][v] for v in graph[u]} for u in graph}
    
    # 使用BFS寻找增广路径
    def bfs(residual_graph, source, sink, parent):
        visited = {u: False for u in residual_graph}
        queue = [source]
        visited[source] = True
        
        while queue:
            u = queue.pop(0)
            for v in residual_graph[u]:
                if not visited[v] and residual_graph[u][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
        return False
    
    parent = {u: -1 for u in residual_graph}
    
    # 不断寻找增广路径并更新流量
    while bfs(residual_graph, source, sink, parent):
        path_flow = float('inf')
        v = sink
        # 计算增广路径上的最小残量
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, residual_graph[u][v])
            v = u
        
        # 更新残量网络
        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= path_flow
            residual_graph[v][u] += path_flow
            v = u
        
        max_flow += path_flow
    
    return max_flow
</syntaxhighlight>

=== 输入与输出示例 ===
假设有以下网络流图（用邻接矩阵表示）：
<syntaxhighlight lang="python">
graph = {
    's': {'a': 10, 'b': 5},
    'a': {'b': 2, 'c': 4, 'd': 8},
    'b': {'d': 9},
    'c': {'t': 10},
    'd': {'c': 6, 't': 10},
    't': {}
}
</syntaxhighlight>

运行 `ford_fulkerson(graph, 's', 't')` 后，输出最大流为：
<syntaxhighlight lang="text">
19
</syntaxhighlight>