编辑“︁Ford-Fulkerson算法”︁

{{DISPLAYTITLE:Ford-Fulkerson算法}}

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

== 算法介绍 ==

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

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

数学上，残量 <math>c_f(u, v)</math> 定义为：
<math>c_f(u, v) = c(u, v) - f(u, v)</math>
其中：
* <math>c(u, v)</math> 是边 <math>(u, v)</math> 的容量。
* <math>f(u, v)</math> 是当前流量。

反向边的残量为 <math>c_f(v, u) = f(u, v)</math>。

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

== 算法步骤 ==

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>

== 实际案例 ==

Ford-Fulkerson算法在现实中有广泛的应用，例如：
* '''交通网络流量优化'''：计算城市道路网络中从起点到终点的最大车流量。
* '''计算机网络'''：确定数据包在网络中的最大传输速率。
* '''电力分配'''：优化电网中电力的传输路径。

=== 示例：计算机网络中的带宽分配 ===
假设一个数据中心需要将数据从服务器 <math>S</math> 传输到服务器 <math>T</math>，中间经过多个路由器，每条链路的带宽有限。使用Ford-Fulkerson算法可以计算出从 <math>S</math> 到 <math>T</math> 的最大数据传输速率。

== 复杂度分析 ==

Ford-Fulkerson算法的时间复杂度取决于增广路径的选择方法：
* 如果使用BFS（即Edmonds-Karp算法），时间复杂度为 <math>O(VE^2)</math>，其中 <math>V</math> 是顶点数，<math>E</math> 是边数。
* 如果增广路径选择不当（如使用DFS），算法可能无法在多项式时间内终止，尤其是在边容量为无理数时。

== 可视化示例 ==

以下是一个网络流图的残量网络示例：
<mermaid>
graph LR
    s((s)) -->|10/10| a((a))
    s -->|5/5| b((b))
    a -->|2/2| b
    a -->|4/4| c((c))
    a -->|8/8| d((d))
    b -->|9/9| d
    c -->|10/10| t((t))
    d -->|6/6| c
    d -->|10/10| t
</mermaid>

== 总结 ==

Ford-Fulkerson算法是解决最大流问题的经典方法，其核心是通过残量网络和增广路径逐步逼近最大流。虽然算法简单直观，但实际应用中需要注意选择合适的增广路径方法（如BFS）以保证效率。该算法在网络优化、运输调度等领域具有重要价值。

== 参见 ==
* [[Edmonds-Karp算法]]
* [[Dinic算法]]
* [[网络流问题]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]