老城区的地下水管网已经用了三十年。水库 S 在城东，新建的蓄水池 T 在城西，中间是织满大街小巷的管道网。每一段管道都有直径限制，水只能沿固定方向前进；老检修工王师傅的任务，是在雨季前算清楚一天最多能往蓄水池送多少水。这听起来是个水管问题，但它其实是一类数学模型的化身——网络流。把管道换成有容量的边，把阀门换成节点，把“最多能送多少水”换成最大流，就是我们要解的题。EK（Edmonds-Karp）和 Dinic 是两套经典解法：EK 像维修队每次走“管子数量最少”的路线送水，Dinic 像先给整张管网画好海拔分层再一口气灌满所有可用通道。理解它们，你不仅能算出最大流，还能看清许多调度、分配、匹配问题的本质。
对 AI 从业者而言，网络流是任务分配、资源调度、图匹配等组合优化问题的“最强大脑”；看懂 EK 与 Dinic，你就知道在数据规模变大时该用哪把扳手，也更容易理解编译器、分布式系统中那些隐藏的最优化决策。
可视化演示
网络流算法用于求解最大流问题，Edmonds-Karp基于BFS增广路复杂度为O(VE^2)，Dinic利用分... 切换模式查看不同维度。
本节配有交互动效（进入视口后自动加载，约 3KB）。
最大流问题与：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现
网络流基础
王师傅拿到管网图后，第一件事不是急着开闸，而是给每个中间阀门贴一张规则牌：“进来的水必须等于出去的水，一滴都不能囤。”水库能供水，蓄水池能接收，中间节点只是透明的分流站。这个朴素的生活规则，正是网络流最核心的骨架。
把地图抽象成数学对象：有向图 G=(V,E) 中的顶点是阀门，边是管道，容量 c(u,v) 是管道粗细，流量 f(u,v) 是实际送水量。除了源点 s 和汇点 t，任何中间节点都不能凭空产生或吞掉水。于是网络流问题就是在遵守下列规则的条件下，让从 s 到 t 的总流量最大。
回到地图上，王师傅把规则贴在墙上后，真正的工程才开始：他需要一套系统方法，反复寻找还能送水的路线，直到整个管网再也挤不出更多水。
- 流量非负
f(u,v) \ge 0：水不能倒灌，任何管道的实际流量不能为负数。 - 容量上界
f(u,v) \le c(u,v)：管道粗细决定了单条管线最多能通过多少水。 - 流量守恒
\sum_{(u,v)\in E} f(u,v) = \sum_{(v,w)\in E} f(v,w)：对每个中间节点，流入量必须恰好等于流出量，水既不能积压也不能凭空出现。 - 最大流目标
\max |f|：在所有可行方案中，选择从源点送到汇点总水量最大的那个。
残留网络
老王每送完一轮水，都会在图纸上用两种颜色做记录：红色标出“这根管道还能加多少”，蓝色标出“之前送的量能不能退回来”。这张记录当前所有“可操作空间”的动态图纸，就是残留网络。
技术上说，如果边 (u,v) 已经流了 f(u,v)，那么在残留网络 G_f 中，正向边还剩下 c_f(u,v)=c(u,v)-f(u,v) 的容量；同时要添加一条反向边 c_f(v,u)=f(u,v)，它不代表物理倒流的管道，而是“撤销额度”——允许我们退回之前错误分配的水。没有反向边，很多一开始选错路线的方案就永远无法修正。
老王把红色和蓝色标满整张图后，找路就变成了看“哪里有连续的红色或蓝色箭头能从 S 连到 T”。这张动态图纸，是所有增广路算法的舞台。
- 正向余量
c_f(u,v)=c(u,v)-f(u,v)：管道还没用满的部分，是未来还能增加的流量空间。 - 反向余量
c_f(v,u)=f(u,v)：已经送出的流量可以被撤销的上限，等价于把之前某一步的决策改回去。 - 可增广路
P: s \rightsquigarrow t：在残留网络中存在从源点到汇点的路径时，当前流就还没有达到最大。 - 路径容量
P上所有边的c_f都为正值：这条路才真正“走得通”。
增广思想
既然残留网络里已经画出了所有“还能走的路”，接下来就简单了：每次找到一条从 S 到 T 的可增广路，把这条路上最窄管道的剩余容量作为增量 δ 加上去。为什么要取最小值？因为一条管线的输送能力由最细的一段决定，这就是瓶颈。
一轮增广之后，残留网络会立刻变化：正向边被用掉一些，反向边被记下新账。于是再找下一条路，再增广，直到整个残留网络里再也找不到从 S 到 T 的路径。此时由增广路定理与最大流最小割定理可知，当前流量已经达到最大值——不是“暂时找不到路”，而是任何继续增加流量的方案都会被某个最小割的管道瓶颈挡住。
王师傅发现，这个“找路—加量—再看图”的思路谁都能听懂，但如何找路、找多少次，直接决定了效率。于是他准备了两套施工方案。
- 瓶颈增量
\delta=\min_{(u,v)\in P} c_f(u,v)：整条增广路的可加水量等于所有残留容量中的最小值。 - 正向加流
f'(u,v)=f(u,v)+\delta：沿原始管道方向增加流量，记入新的实际送水量。 - 反向减流
f'(u,v)=f(u,v)-\delta：若路过反向边，则等价于撤销之前的一部分流量，而不是物理倒水。 - 终止判定残留网络中不存在从
s到t的路径：当前方案已经是最大流，继续寻找不会再有任何收益。
EK算法
王师傅的第一套方案很笨但可靠：每次从水库出发，用 BFS 按“经过的管道根数最少”找一条到蓄水池的路线。为什么必须是最短路线？因为如果任选一条可行路就送水，可能绕来绕去浪费大量轮次；而 BFS 保证每轮增广后，源点到汇点的最短距离单调不减，整体增广次数被压缩到 O(VE) 以内。
EK 算法实现起来几乎是直觉的：维护一个残留容量矩阵，每次 BFS 找增广路并记录前驱，然后沿路径找到瓶颈增量，再正向减、反向加地更新残留网络。当 BFS 再也到不了汇点时，算法结束。它的最坏时间复杂度是每次 BFS 的 O(E) 乘以最多 O(VE) 次增广。
老王的体会是：EK 像“宁可多跑几趟也要保证每趟都是最短路线”，适合管道不多的小片区；一旦整张地图变得密密麻麻，就该换第二套方案。
- 单次 BFS 成本
O(E)：在残留网络里用队列扩展所有可达顶点，需要扫描全部边。 - 增广次数上界
O(VE)：每轮至少让一条关键边的残留容量降为 0，而路径长度变化受顶点数限制。 - 总复杂度
O(VE^2)：把每一轮 BFS 的代价与轮数相乘，得到最坏运行时间。 - 空间复杂度
O(E)：只需要保存残留容量矩阵和 BFS 的前驱数组。
Dinic算法
第二种方案高级得多：先用 BFS 给整个管网画海拔线——从源点出发，算出每个节点到源点的最短距离，这就是分层图；然后规定水只能从低层流向高一层，绝不走回头路。在这个有向无环的层次结构里，用 DFS 一次找出所有能走的路，直到无法向更高层推进，形成一轮阻塞流。之后重新画海拔线，再来下一轮。
Dinic 的核心优势是把“找一条路”升级成“一次找一批路”。每轮 BFS 建图成本是 O(E)，一轮 DFS 找阻塞流在当前弧优化下是 O(VE)；而层次图每轮都会让最短路径至少增加 1，所以阶段数不超过 O(V)。由此得到最坏复杂度：
对老王来说，Dinic 就像看了整体地形才动手：先分层，再批量送水，明显比 EK 一趟趟跑更省时间。而在一种特殊地形里，Dinic 的优势还会被进一步放大。
- 建层次图
O(E)：一次 BFS 就能给所有顶点标出到源点的最短距离层号。 - 找阻塞流
O(VE)：DFS 沿着层号严格递增的方向多路搜索，当前弧优化保证每条边每阶段最多被检查一次。 - 阶段数上界
O(V)：每完成一个阶段，源点到汇点的最短距离至少增加 1，最多增加到V-1。 - 总复杂度
O(V^2E)：阶段数乘以每阶段成本，得到最坏情况下的时间上界。
单位网络
如果整张管网里每根管道都一样粗，并且容量恰好为 1，问题就变成单位网络。最典型的场景是二分图最大匹配：源点连左部顶点、右部顶点连汇点，容量全为 1；左部到右部的匹配边也设容量 1。每一单位流量都代表一个配对，最大流就是最大匹配数。
单位容量带来一个特殊红利：每条增广路只能携带 1 单位流量，且层次图中每条路径都很“窄”。于是阶段数的理论上界从一般网络的 O(V) 收紧到 O(\sqrt V)，每阶段仍为 O(E)，总复杂度变成：
正因为单位网络有如此漂亮的复杂度，二分图匹配、任务分配这类“一对一”问题在工程中都愿意建模成网络流，再交给 Dinic 求解。
- 单位容量限制
f(e)\in\{0,1\}：每条边要么空着，要么被一单位流量占满，单次增广增量恒为 1。 - 阶段数上界
O(\sqrt V)：前 √V 个阶段后，残留增广路必须变得足够长，路径条数受剩余顶点数限制。 - 每阶段成本
O(E)：单位网络的 BFS 与 DFS 依然只需扫描一遍边。 - 总复杂度
O(E\sqrt V)：每阶段O(E)，阶段数O(\sqrt V)，两者相乘。
对比应用
两套方案到底怎么选？老王总结出一条经验：看地形。边数很少的稀疏管网，EK 写起来简单、验证快，虽然理论复杂度不高，但常数小；边数多、顶点多的稠密网络，Dinic 的分层灌水法明显更占优，尤其是单位网络场景，Dinic 能把复杂度压到 O(E√V)，几乎是一般网络的特快通道。
把两个复杂度放在一起看：
老王最终把两把扳手都放进了工具箱：遇到复杂地形，先建模，再根据图的形态选择算法。看懂这两套方案，你也就掌握了网络流从理论到工程落地的完整地图。
- EK 的瓶颈
O(VE^2)：边越多，BFS 的轮数和每轮的扫描成本同时上升，平方项来自E。 - Dinic 的瓶颈
O(V^2E)：最坏阶段的次数由顶点数V主导，边数只以一次方出现。 - 稀疏图选 EK
E\approx V：两者量级相近，EK 实现更直接，适合快速原型。 - 稠密/单位图选 Dinic
E\sqrt V远小于VE^2：网络越密、容量越规整，Dinic 优势越明显。
AI 应用场景
云平台任务调度
阶段：数据/算力资源调度
解决的问题：传统的贪心调度容易陷入局部最优，导致某些 GPU 空闲、某些任务排队。把“任务—GPU 可运行关系”建模成二分图，用单位网络上的 Dinic 求最大匹配，可以一次性得到最多能同时执行多少个任务。
具体案例：一个推理平台有 1000 个预处理任务和 800 个 GPU 实例，每个任务只能在部分 GPU 上运行。把源点连任务、任务连可用 GPU、GPU 连汇点，容量全为 1，跑一遍 Dinic 就能得到最大并行分配数，并快速定位哪些任务无法被满足。
数据中心流量调度
阶段：训练集群带宽分配
解决的问题：大模型分布式训练时，多张显卡需要同步梯度，主链路经常成为瓶颈。把机房链路抽象成流网络，用最大流算法计算从参数服务器到工作节点的最大可用带宽，能清晰看出哪些链路需要扩容。
具体案例：在某 BERT 预训练任务中，64 张卡同步梯度时总带宽不足。工程师将交换机的每根链路设成带容量边，用 EK 快速验证小规模拓扑，再用 Dinic 在完整拓扑上找到瓶颈割，最终通过调整通信拓扑让一轮同步时间缩短 30%。
编译器寄存器分配
阶段：编译优化与后端代码生成
解决的问题：编译器要把大量活跃变量映射到有限寄存器上，本质是一个匹配问题。把“变量生命周期”和“寄存器槽位”建模成二分图，用单位网络最大流估算最多能同时放入寄存器的变量数，能帮助决定何时触发寄存器溢出。
具体案例：在 LLVM 后端的寄存器压力分析中，某个热循环有 40 个活跃变量但只有 16 个可用寄存器。通过二分图最大匹配先算出可驻留寄存器的上限，再配合启发式染色，显著减少了内存加载指令。
Python 演示
from collections import deque def edmonds_karp(cap, s, t): n = len(cap) flow = 0 while True: prev = [-1] * n prev[s] = s q = deque([s]) while q and prev[t] == -1: u = q.popleft() for v in range(n): if cap[u][v] > 0 and prev[v] == -1: prev[v] = u q.append(v) if prev[t] == -1: return flow add = 10 ** 9 v = t while v != s: u = prev[v] add = min(add, cap[u][v]) v = u v = t while v != s: u = prev[v] cap[u][v] -= add cap[v][u] += add v = u flow += add def dinic(edges, n, s, t): graph = [[] for _ in range(n)] def add_edge(u, v, c): graph[u].append([v, c, len(graph[v])]) graph[v].append([u, 0, len(graph[u]) - 1]) for u, v, c in edges: add_edge(u, v, c) level = [-1] * n it = [0] * n def bfs(): for i in range(n): level[i] = -1 q = deque([s]) level[s] = 0 while q: u = q.popleft() for v, c, r in graph[u]: if c > 0 and level[v] < 0: level[v] = level[u] + 1 q.append(v) return level[t] >= 0 def dfs(u, f): if u == t: return f while it[u] < len(graph[u]): e = graph[u][it[u]] v, c, r = e if c > 0 and level[v] == level[u] + 1: ret = dfs(v, min(f, c)) if ret: e[1] -= ret graph[v][r][1] += ret return ret it[u] += 1 return 0 ans = 0 while bfs(): it = [0] * n while True: f = dfs(s, 10 ** 9) if not f: break ans += f return ans if __name__ == '__main__': edges = [(0, 1, 10), (0, 2, 5), (1, 3, 8), (2, 3, 5)] cap = [[0] * 4 for _ in range(4)] for u, v, c in edges: cap[u][v] += c print('EK :', edmonds_karp(cap, 0, 3)) print('Dinic:', dinic(edges, 4, 0, 3))
if cap[u][v] > 0 and prev[v] == -1:BFS 只在仍有剩余容量且顶点未访问时才前进，这正是残留网络上的可增广路搜索。add = min(add, cap[u][v])沿路径找出最小值，对应“最细管道决定整条路能送多少水”的瓶颈思想。cap[u][v] -= add正向边减去本次增广量，更新残留容量。cap[v][u] += add反向边加上同样的量，记录未来可以撤销的额度。graph[u].append([v, c, len(graph[v])])存储正向边的同时记下反向边在邻接表中的位置，方便 O(1) 更新。if c > 0 and level[v] == level[u] + 1:DFS 只沿层次图逐级前进，保证水始终从低层流向高一层。it[u] += 1当前弧优化：这条边已经饱和或无效，下一阶段直接跳过，避免重复检查。while bfs():每成功建一次层次图，就开启 Dinic 的一个新阶段。f = dfs(s, 10 ** 9)从源点发起多路阻塞流搜索，一次返回一条增广增量。print('EK :', edmonds_karp(cap, 0, 3))在小图上对比两种算法的输出，验证它们得到相同最大流。
常见误区
误区残留网络里的反向边代表水真的可以倒流回去，所以实际工程中要实现双向管道。
正解反向边只是算法层面的“撤销额度”，表示我们可以退回之前分配的流量，从而修正早期错误决策。物理上水流方向始终由原始有向边决定。就像送水单可以改签，但不代表已经送出去的水会倒流回家。
为何常见：残留网络画出来和原图一样是有向箭头，初学者很容易把“虚拟记账”误认为“物理管道”。
误区既然是找一条可行路径，用 BFS 还是 DFS 没区别，反正都能到达汇点。
正解EK 的复杂度保证完全依赖 BFS 找到的“最短（边数最少）增广路”。如果改用 DFS 随意找，最坏情况下增广次数可能变成指数级，算法会彻底退化。就像维修队不按最短路线走，绕路次数会失控。
为何常见：小图上 DFS 往往是“能到达汇点”的，于是让人误以为路径选择无所谓。
误区分层图建好之后，DFS 每次递归都要重新检查所有邻接边，反正图不大。
正解Dinic 必须配合当前弧优化：每个顶点的边指针只前进不后退，已经饱和或无法推进的边在本阶段不再检查。没有这个优化，阻塞流搜索会退化成大量重复扫描，复杂度失去保证。
为何常见：初学者只关注“分层”这个直观概念，忽略了“当前弧”才是让每边只处理一次的关键工程细节。
误区水库出口的管道容量加起来是多少，最大流就应该是多少。
正解源点出边容量只是上界之一，整个网络还可能被中间管道或汇入汇点的边卡住。最大流等于最小割容量，割可以出现在任意位置。就像水库出口再粗，通往城西的主水管不够粗，水照样送不过去。
为何常见：看到源点出边最多就以为瓶颈只在源头，忽略了网络中“最窄处”往往藏在中间。
面试题
Q1. 在流网络中，除源点和汇点外，任意中间节点必须满足什么条件？
- A.流入量大于流出量
- B.流入量等于流出量← 正确答案
- C.流入量小于流出量
- D.无需任何限制
答案：B。中间节点不能囤水也不能凭空产水，流入必须等于流出。这对应“流量守恒”，就像阀门只是分流站，不存水。A、C 都会造成水堆积或消失，D 则完全违背规则。
Q2. 残留网络中的反向边容量表示什么？
- A.原来管道能承受的最大额外流量
- B.已经沿正向边输送的流量，也就是可以撤销的量← 正确答案
- C.从汇点流向源点的实际流量
- D.未被使用的正向容量
答案：B。反向边容量等于当前已发送流量 f(u,v)，代表我们可以退回多少水。它不是真实物理管道，而是算法里的“改签额度”。A 是正向剩余容量，D 也是正向概念，C 是错误理解。
Q3. 最大流最小割定理说明什么？
- A.最大流等于最小割容量← 正确答案
- B.最大流等于所有边容量之和
- C.最小割等于源点出边之和
- D.最大流与割无关
答案：A。定理核心是最大流值恰好等于一个最小割的容量。也就是说，网络的最大输送能力被某个最窄的“切口”完全决定，而不是所有边容量之和。
Q4. EK 算法为什么必须用 BFS 找增广路？
- A.BFS 一定能找到容量最大的路径
- B.BFS 能找到边数最少的增广路，保证增广次数为 O(VE)← 正确答案
- C.BFS 能避免使用反向边
- D.BFS 可以在 O(1) 内完成
答案：B。EK 的复杂度证明依赖“每次找最短增广路”这一性质，它让残留网络中源汇最短距离单调增加，从而限制增广轮数。BFS 正好保证这一点，DFS 则没有这个理论保证。
Q5. Dinic 算法中“当前弧优化”主要解决什么问题？
- A.减少 BFS 层次图的构建次数
- B.避免 DFS 反复检查已经饱和或无效的边← 正确答案
- C.保证残留网络中没有反向边
- D.让源点的出边永远优先被选择
答案：B。当前弧优化让每个顶点的边指针只前进不后退，已经榨干或无法增广的边在同一阶段不再检查。它不改变 BFS 次数，也不消除反向边，而是加速阻塞流搜索。
Q6. 在把二分图最大匹配建模为网络流时，连接源点到左侧顶点的边容量通常设为？
- A.该顶点的度数
- B.1← 正确答案
- C.所有边容量之和
- D.无穷大
答案：B。单位网络里每个左部顶点最多匹配一次，所以源点到左部的边容量为 1。右部到汇点同样为 1。这保证一条流量最多对应一个配对。
Q7. 单位容量网络上 Dinic 的时间复杂度是？
- A.O(VE)
- B.O(V^2 E)
- C.O(E√V)← 正确答案
- D.O(V^3)
答案：C。单位容量让每条增广路最多携带 1 单位流量，阶段数从 O(V) 收紧到 O(√V)，每阶段 O(E)，因此总复杂度为 O(E√V)。这也是二分图匹配中 Dinic 高效的原因。
Q8. 一个有 V 个顶点、E 条边的流网络，EK 算法的最坏时间复杂度是？
- A.O(VE)
- B.O(V^2 E)
- C.O(VE^2)← 正确答案
- D.O(E^2)
答案：C。EK 的每轮 BFS 是 O(E)，而增广轮数上界是 O(VE)，两者相乘得到 O(VE^2)。边数越稠密，EK 越吃亏，这也是工程中常选 Dinic 的原因。
Q9. 下列关于 Dinic 算法步骤的描述，正确的有哪些？
- A.用 BFS 构建从源点到各顶点的分层图← 正确答案
- B.DFS 在分层图中反复寻找阻塞流← 正确答案
- C.一个阶段只允许增广一条路径
- D.当前弧优化可加速阻塞流搜索← 正确答案
答案：ABD。Dinic 先用 BFS 分层，再用 DFS 一次找多条路径直到形成阻塞流，所以一个阶段会增广多条路径，C 错误。当前弧优化避免重复扫描边，确实是关键加速手段。
Q10. 为什么 Dinic 在单位网络中的复杂度优于一般网络？
- A.单位网络中所有边容量都是 1，阻塞流每次增广的增量恒为 1
- B.单位网络的层次图深度最多为 2
- C.单位网络中每条边都被看作残留网络的正向边，没有反向边
- D.阶段数理论上界从 O(V) 降到 O(√V)，总复杂度成为 O(E√V)← 正确答案
答案：D。A 说的是单位容量带来的表面现象，但真正让复杂度变优的是阶段数上界从 O(V) 收紧到 O(√V)，再乘每阶段 O(E)，得到 O(E√V)。B 和 C 都对单位网络理解错误。