Ford-Fulkerson算法

Ford-Fulkerson算法是一种用于计算网络流中最大流的经典算法，由L. R. Ford Jr.和D. R. Fulkerson于1956年提出。该算法通过不断寻找增广路径来逐步增加流量，直到无法找到新的增广路径为止，此时得到的流即为最大流。

算法介绍[编辑 | 编辑源代码]

Ford-Fulkerson算法的核心思想是：

初始化网络中所有边的流量为0。
在残量网络（Residual Network）中寻找一条从源点（source）到汇点（sink）的路径（称为增广路径）。
计算该路径上的最小残量（即路径上剩余容量的最小值），并沿着该路径增加流量。
重复上述步骤，直到无法找到新的增广路径为止。

残量网络[编辑 | 编辑源代码]

残量网络是原网络的一个变体，其中每条边的残量（residual capacity）定义为该边的容量减去当前流量。如果残量为正，则表示可以继续增加流量。此外，残量网络还包含反向边，用于表示“回退”流量。

数学上，残量 $c_{f} (u, v)$ 定义为： $c_{f} (u, v) = c (u, v) - f (u, v)$ 其中：

$c (u, v)$ 是边 $(u, v)$ 的容量。
$f (u, v)$ 是当前流量。

反向边的残量为 $c_{f} (v, u) = f (u, v)$ 。

增广路径[编辑 | 编辑源代码]

增广路径是残量网络中从源点到汇点的一条路径，其上的所有边的残量均大于0。通过增广路径可以增加流量，增加的量为该路径上的最小残量。

算法步骤[编辑 | 编辑源代码]

Ford-Fulkerson算法的伪代码如下：

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

输入与输出示例[编辑 | 编辑源代码]

假设有以下网络流图（用邻接矩阵表示）：

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': {}
}