网络流算法详解 | AI生成和翻译

Home 2025.10 English 中文

---

网络流算法解析

网络流算法是图论和计算机科学中的基础课题，用于建模和解决涉及资源在网络中流动的问题（如管道、道路或数据流）。它们对优化任务至关重要，例如最大流（如管道系统能输送的最大水量）、最小割（如寻找瓶颈）以及在运输、调度和匹配中的应用。

我将逐步解析：核心概念、简单示例、主要算法及深入学习建议。我们将重点讨论最大流问题，因为这是核心所在。

1. 核心概念

• 图表示：网络是一个有向图 \( G = (V, E) \)，包含顶点 \( V \)（节点）和边 \( E \)（连接）。每条边具有容量 \( c(u, v) \)，表示从节点 \( u \) 到 \( v \) 能承载的最大流量。
• 源点与汇点：一个节点是源点 \( s \)（流量起点），另一个是汇点 \( t \)（流量终点）。
• 流量：函数 \( f(u, v) \) 为每条边分配流量，需满足：
  • 容量约束：\( 0 \leq f(u, v) \leq c(u, v) \)。
  • 守恒性：对于非 \( s \) 或 \( t \) 的节点，流入量等于流出量（无累积）。
• 净流量：流量具有反对称性：\( f(u, v) = -f(v, u) \)。
• 残差图：记录发送流量后的剩余容量。若在容量为 \( c \) 的边上发送流量 \( f \)，则正向残差容量为 \( c - f \)，反向残差容量为 \( f \)（用于”撤销”流量）。
• 目标：
  • 最大流：最大化从 \( s \) 到 \( t \) 的总流量。
  • 最小割：将节点划分为包含 \( s \) 的集合 \( S \) 和包含 \( t \) 的集合 \( T \)；最小化从 \( S \) 到 \( T \) 的容量总和。根据最大流最小割定理，最大流等于最小割容量。

2. 简单示例

假设一个货物运输的小型网络：

• 节点：\( s \)（源点）、A、B、\( t \)（汇点）。
• 边：
  • \( s \to A \)：容量 10
  • \( s \to B \)：容量 10
  • \( A \to B \)：容量 2
  • \( A \to t \)：容量 8
  • \( B \to t \)：容量 9

ASCII 可视化：

  s
 / \
10  10
A   B
| \ / |
8  2  9
 \ /  
  t

最大流是多少？直观来看，向 A 和 B 各发送 10，但 A 只能向 t 推送 8（2 流向 B，帮助 B 推送 9+2=11，但 B 的限制是 9？稍等，我们精确计算一下。

使用算法（见下文）后，最大流为 17：

• 路径 1：s→A→t（流量 8），更新残差。
• 路径 2：s→B→t（流量 9），更新残差。
• 路径 3：s→A→B→t（流量 0？第一次后 A 有 2 剩余流向 B，但 B 到 t 的剩余容量为 0——实际上需要调整。

更准确的说法：从 s 出发的总流量为 20，但瓶颈限制为 17（8 直接从 A 流出 + 9 从 B 流出，其中 2 被重新路由？不——运行算法以获得精确值。

3. 主要算法

从基础开始，逐步构建至高效算法。所有算法均通过在残差图中沿路径增广流量，直到不存在增广路径为止。

• Ford-Fulkerson 方法（1956，基础性）：
  • 在残差图中重复寻找从 s 到 t 的任意路径（如通过 DFS/BFS）。
  • 沿该路径增广最小残差容量对应的流量。
  • 重复直到无路径可用。

  • 时间复杂度：取决于实现；若容量为无理数可能很慢（但整数容量下为 O(

    E

    * max_flow)）。

  • 优点：简单。缺点：对大型图效率低。
  • 伪代码：

    while 残差图中存在从 s 到 t 的路径 P:
        瓶颈 = P 上的最小残差容量
        沿 P 增广瓶颈流量
        更新残差
    return 总流量
    

• Edmonds-Karp（1972，Ford-Fulkerson 的 BFS 变体）：
  • 使用 BFS 寻找最短增广路径（避免长路径）。

  • 时间复杂度：O(

    V

    *

    E

    ^2)——多项式时间，适用于小型图。

  • 适合学习；可用约 50 行代码实现。
• Dinic 算法（1970，更高效）：
  • 通过 BFS 构建层次图（按与 s 的距离分层）。
  • 使用 DFS 寻找阻塞流（每层多路径）。

  • 时间复杂度：最坏情况 O(

    V

    ^2 *

    E

    )，但单位容量下为 O(

    V

    *

    E

    )；实际应用中非常快速。

  • 适用场景：中型至大型图。
• Push-Relabel（或 Preflow-Push）（1980 年代，Goldberg-Tarjan）：
  • 使用启发式方法将节点的超额流量”推”向汇点。

  • 时间复杂度：O(

    V

    ^3) 或使用 FIFO/间隙启发式更优。

  • 优点：处理超大规模图（如互联网路由）。

对于最小割：在计算最大流后，割集为最终残差图中从 s 可达的节点与其他节点。

4. 实现建议

• 使用邻接表表示图。
• 代码中（类 Python）：用字典的字典表示残差容量。
• 库：NetworkX（Python）内置如 maximum_flow 的函数。
• 在小例子上测试；使用 Graphviz 等工具可视化。

5. 常见陷阱与扩展

• 循环：残差图通过”回流”处理调整。
• 多源点/汇点：添加超源点/超汇点。
• 成本：对于最小费用流，添加边成本并使用连续最短路径算法。
• 应用：航班调度、图像分割（视觉）、二分匹配（设流量=1）。

学习路径

• 阅读 CLRS（Cormen 等人著作）第 26 章。
• 在 LeetCode/HackerRank 上练习（如”Minimum Cost to Make at Least One Valid Path”）。
• 可视化：在每次增广后绘制残差图。

网络流简介
最大流最小割定理
NetworkX 教程

---

Back

x-ai/grok-4-fast

Donate