网络流(3)：时间复杂度

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为Edmonds-Karp算法、Dinic算法和Hopcroft–Karp–Karzanov算法。

Edmonds-Karp 算法

算法设计

• 改进点：用 BFS 选择增广路径

关键性质

• $G^f$ 中任意顶点 $u$ 到源点的距离 $dist(u)$ 单调不减
• 每次增广导致 $G^f$ 中至少一条边被饱和（称为关键边）
• 原边 $(u, v)$ 两次成为关键边后 $u$ 到源点的距离至少增加 $2$
  • $\mathrm{dist}^{i + j}(u) = \mathrm{dist}^{i + j}(v) + 1 \ge \mathrm{dist}^i(v) + 1 = \mathrm{dist}^i(u) + 2$

时间复杂度

• 每条边成为关键边的次数：$O(|V|)$
• 总迭代次数：$O(|V| \cdot |E|)$
• 每次迭代的时间：$O(|E|)$
• 总时间复杂度：$O(|V| \cdot |E|^2)$

Edmonds-Karp 算法可以处理容量是无理数的情况。

Dinic 算法

关键思想

• 核心思路：每一轮将 $t$ 到源点的距离 $dist(t)$ 增大 $1$
• 分层图 (Level Graph)：仅保留从源点出发按 BFS 层数递增的边
• 阻塞流 (Blocking Flow)：分层图中无法再找到增广路径的流

算法步骤

• 初始化流 $f$ 为空，残差网络 $G^f$ 为 $G$
• 重复以下步骤，直到 $dist(t) = \infty$
  • 从 $G^f$ 构建分层图 $G_L^f$
  • 用 DFS 在分层图中寻找阻塞流
  • 更新流 $f$ 和残差网络 $G^f$

关键性质

• 每次 DFS 搜索后至少一条边被移除（关键边或回溯边）
• $G_L^f$ 中所有长度为 $\mathrm{dist}^i(t)$ 的路均被阻塞，从而 $\mathrm{dist}^{i + 1}(t) > \mathrm{dist}^i(t)$

时间复杂度

• 每次搜索最多步数：$O(|V|)$
• 每次迭代中搜索次数：$O(|E|)$
• 每次迭代的时间：$O(|V| \cdot |E|)$
• 迭代次数：$O(|V|)$
• 总时间复杂度：$O(|V|^2 \cdot |E|)$

Hopcroft-Karp-Karzanov 算法

算法思想

• 将二分图最大匹配转化为最大流问题（所有边容量为1），应用 Dinic 算法
• 时间复杂度为 $O(|E| \cdot \sqrt{|V|})$

寻找阻塞流

• 由于每条边容量为 $1$，找阻塞流只需要一次 DFS
• 每次寻找阻塞流的时间复杂度为 $O(|E|)$

迭代轮数

• 对每个非 $s$ 或 $t$ 的点，其入度或出度始终为 $1$
• $G^f$ 中的最大流等于 $G^f$ 中点不相交（vertex-disjoint）路的数量
• $\sqrt{|V|}$ 轮后，$G^f$ 中的最大流最多是 $\sqrt{|V|}$
• 从而再过 $\sqrt{|V|}$ 轮后，算法终止，即总迭代轮数最多 $2 \sqrt{|V|}$

网络流算法总结

算法	时间复杂度	核心思想	适用场景
Ford-Fulkerson	$O(\vert E \vert \cdot f_{max})$	任意增广路径	理论分析
Edmonds-Karp	$O(\vert V \vert \cdot \vert E \vert ^2)$	BFS 选择增广路径	稀疏图
Dinic	$O(\vert V \vert ^2 \cdot \vert E \vert)$	分层图 + 阻塞流	稠密图
Hopcroft-Karp-Karzanov	$O(\vert E \vert \cdot \sqrt{\vert V \vert})$	Dinic 在二分图中应用	二分图最大匹配

注：本文中所有图片均来自张宇昊老师的课程PPT。