最大流算法对比：EK、Dinic 与 ISAP

可视化演示

最大流问题有多种经典算法，Edmonds-Karp简单易懂基于BFS，ISAP通过间隙优化与当前弧优化提升效率... 切换模式查看不同维度。

问题定义：给水管网建模

作为供水总调度，你面对的其实是一张“有方向的管网图”：水库只有一个出口，用 S 表示源点；居民区只有一个总入口，用 T 表示汇点；中间每个泵站是一个节点，每根管道是一条有向边。管道粗细决定了水的上限，数学上称为“容量”。你的目标，是算出从 S 到 T 每秒最多能送多少吨水。把复杂管网抽象成图模型后，这个问题就有了精确的数学表达。

在图论中，最大流问题定义为：给定有向图 $G=(V,E)$，每条边 $(u,v)$ 有一个非负容量 $c(u,v)$，指定源点 $s$ 与汇点 $t$，求从 $s$ 出发能够到达 $t$ 的最大流量。除了容量限制，水流还必须满足“守恒定律”——中间节点既不能凭空产水，也不能偷偷存水，流进来的必须等于流出去的。正是这两条规则，把“送水问题”变成了一个可计算的优化模型。

把管网“翻译”成这套符号之后，问题就清晰了：所有算法都在回答同一个问题——如何在容量和守恒的双重约束下，逼近甚至严格达到最大流量。接下来出场的三种算法，就是三种性格迥异的调度方案，它们的效率差异，正是这篇文章要讲的重点。

EK算法：老实调度员的最短增广

最朴素的调度员是怎么干的？他手上有一张管网全图，每次送水前，先用最笨也最稳的办法：从水库出发，逐层向外扫描，找到一条“经过泵站数量最少”的路线，然后按下这条路的最大通水量放水。等这条路上有管道满了，再回头重新扫描，换下一条路。这个“逐层扫描找最短路线”的动作，计算机里叫 BFS（广度优先搜索）。这种每次只送一条路、反复 BFS 的算法，就是 Edmonds-Karp 算法，简称 EK。

EK 的核心秘密在于“残余网络”。你可能会想：管道送满了水，不就废了吗？其实不然。算法会给每条边记两笔账：正向记录“还剩多少容量”，反向记录“已经送了多少，可以撤回”。例如管道 $u \to v$ 容量 10，已经送了 7，那么正向容量剩 3，同时多出一条虚拟的“反向管道” $v \to u$ 容量 7。这些正向与反向的剩余容量合在一起，组成残余网络。它给了算法“反悔”的机会——如果后面发现更好的路线，可以把之前送的水退回去重新安排。每一次沿残余网络中的一条路增加流量，称为一次“增广”。

老实调度员的好处是绝不会错——BFS 保证每次都走全局最短路，正确性有严密证明；缺点是效率看运气。如果管道网络设计得刁钻，他可能要来回跑很多趟。但在小规模管网上，这种“老实”恰恰是优点：实现简单、不易写错，是很多工程新手首选的方案。

Dinic算法：分层指挥官的多路推送

比老实调度员更聪明的，是一位“分层指挥官”。他不满足于一次只送一条路，而是先做整体规划：用 BFS 从水库出发，把整个管网按“到源点最少经过几个泵站”分成若干层。比如水库自己是第 0 层，直接相连的泵站是第 1 层，再远一点是第 2 层……水流的规则被限定为“只准从第 $k$ 层流向第 $k+1$ 层”，不许横跳或回流。这张只保留层间前进边的图，就是“分层图”。

分层之后，指挥官派出 DFS（深度优先搜索）在层间反复探路，一口气找出所有能走的路径，把当前分层结构下能送的流量全部推满，直到达到“阻塞流”——即无论怎么走都无法再从源点推水到汇点。然后重新 BFS 分层，再推阻塞流，循环往复。关键在于：每轮分层后，汇点的“层号”至少增加 1，所以最多分层 $O(V)$ 轮；而每轮内部通过 DFS 多路增广，总复杂度降下来了。这就是 Dinic 算法。

分层指挥官的高明之处，是把“全局最短路径”升级成了“全局分层 + 局部多路推送”。他不再纠结于哪条路绝对最短，而是先把地图按距离切开，再在每一层内同时开闸。这种“分而治之”的思路，让 Dinic 在绝大多数场景下比 EK 快一个量级，也让它成为算法竞赛和工程实践中的默认选择。

ISAP算法：老练师傅的双项优化

如果说 Dinic 是科班出身的指挥官，ISAP 就是摸爬滚打多年的老师傅。他沿用了“距离标号”的思路——从汇点反向 BFS 一次，给每个节点标上“到汇点还有多少步”，记为 $d(v)$。此后他不再重新分层，而是在增广的同时动态维护这些距离标号。每次只从当前节点 $v$ 走向满足 $d(v) = d(u) + 1$ 的邻点 $u$，保证每一步都走在“离汇点更近一步”的正确方向上。这是第一项优化：只做一次反向 BFS，省去反复分层。

老师傅还有两个小本本。第一个本子记录“当前弧”：每个泵站上次送水的出水管是哪一根，下次直接从这根之后开始试，绝不重复检查已经饱和的管道，这叫“当前弧优化”；第二个本子记录“间隙”：统计每一层距离标号各有多少个节点。一旦发现某一层一个节点都没有（$gap[i] = 0$），说明网络已经“断层”——水流不可能从源点够到汇点了，立即收工。这个“间隙优化”让算法能提前终止，省掉大量无效试探。这两招合起来，就是 ISAP（Improved Shortest Augmenting Path）的完整形态。

老师傅的经验换来了两个看得见的好处：单次 BFS 初始化后不再全局重扫，加上当前弧优化减少了大量重复边检查，常数极小。它的最坏复杂度和 Dinic 同为 $O(V^2E)$，但实战中常常比 Dinic 快上 10% 到 30%。当然，代价是实现细节更繁琐——距离标号更新、当前弧指针复位、gap 数组维护，每处都得小心翼翼。

性能对比：三张成绩单

把三位调度员放到同一张成绩单上，最直观的对比是“最坏时间复杂度”：EK 是 $O(VE^2)$，Dinic 和 ISAP 都是 $O(V^2E)$。单看渐近记号，后两者全面占优，但问题没这么简单——不同的图结构会改写排名。在二分图最大匹配这类特殊网络上，Dinic 的时间可以降到 $O(E\sqrt{V})$，比通用复杂度整整低一个量级；而在单位容量网络（每条边容量都是 1）上，Dinic 的复杂度进一步优化为 $O(E \min(V^{2/3}, \sqrt{E}))$。EK 虽然没有这些“隐藏技能”，但它在顶点数很小、边数很多时，$VE^2$ 未必比 $V^2E$ 差。

空间开销方面，三者几乎平手，都是 $O(V+E)$ 级别的存储：邻接表加少量辅助数组。真要抠常数，EK 最省，因为它只需要 BFS 队列和父节点数组；Dinic 多一张分层图；ISAP 多一套距离标号和 gap 数组，但差距都在几十 KB 以内。实际表现上，有个经验规律：边数 $E$ 远大于顶点数 $V$ 时，$VE^2$ 会迅速膨胀，Dinic/ISAP 优势明显；顶点数大而边稀疏时，EK 的常数优势会缩小差距，甚至反超。

成绩单看完，结论清晰：没有绝对的王者，只有合适的选手。EK 简单稳健、易于调试，是教学和小规模图的首选；Dinic 综合实力最强，适用面最广；ISAP 常数最优，是大规模流量问题的冲刺型选手。工程上选谁来“送水”，得看管网的规模、形状和你的调试耐心。

工程选型：按图纸挑方案

回到供水调度的日常：这张管网图纸到底该派哪位调度员上场？经验法则可以浓缩成一条公式——总耗时约等于“增广轮数 × 每轮平均成本”。EK 的轮数上界是 $O(VE)$，但每轮只有一个简单的 BFS，成本极低；Dinic 和 ISAP 的轮数上界是 $O(V)$，但每轮要做分层或维护距离标号，成本更高。图小的时候，EK 的“多跑几趟”完全不成问题，反而因为代码短、好维护而胜出；图一大，轮数差距被放大，就必须上 Dinic 或 ISAP。

具体的选型标尺可以按顶点数划定：顶点数 $V \leq 500$ 时，EK 足够，十分钟写完还不容易错；$V$ 到 $10^4$ 级别、边数中等，Dinic 是稳妥之选，它平衡了实现复杂度与运行速度；$V$ 和 $E$ 都很大、且对耗时极度敏感（比如在线评测的极限数据），ISAP 值得你付出额外的实现成本。若是二分图匹配、任务分配这类特殊结构，优先套用 Dinic 的 $O(E\sqrt{V})$ 特例，代码反而更简单。

选型从来不是一道数学题，而是一道工程权衡题。把管网图纸摊开，看清规模与结构，再决定派谁上场——这份判断力，正是你在真实项目中从“会写算法”迈向“会选算法”的关键一步。顺带一提，编译器的指令调度、寄存器分配等底层优化，同样会化归为网络流模型，这套选型思路在系统底层同样适用。

AI 应用场景

Python 演示

# 最大流 Dinic 算法实现class Dinic:    def __init__(self, n):        self.n = n        self.adj = [[] for _ in range(n)]  # 邻接表     def add_edge(self, u, v, cap):        # 正向边记录反向边的下标        self.adj[u].append([v, cap, len(self.adj[v])])        self.adj[v].append([u, 0, len(self.adj[u]) - 1])     def bfs(self, s, t):        self.level = [-1] * self.n        queue = [s]        self.level[s] = 0        for u in queue:            for e in self.adj[u]:                if e[1] > 0 and self.level[e[0]] < 0:                    self.level[e[0]] = self.level[u] + 1                    queue.append(e[0])        return self.level[t] >= 0     def dfs(self, u, t, f):        if u == t:            return f        while self.it[u] < len(self.adj[u]):            e = self.adj[u][self.it[u]]            if e[1] > 0 and self.level[u] + 1 == self.level[e[0]]:                ret = self.dfs(e[0], t, min(f, e[1]))                if ret > 0:                    e[1] -= ret                    self.adj[e[0]][e[2]][1] += ret                    return ret            self.it[u] += 1        return 0     def max_flow(self, s, t):        flow = 0        while self.bfs(s, t):            self.it = [0] * self.n            while True:                f = self.dfs(s, t, float('inf'))                if f == 0:                    break                flow += f        return flow if __name__ == '__main__':    # 构造示例网络: 0=S, 1=A, 2=B, 3=T    dinic = Dinic(4)    dinic.add_edge(0, 1, 10)    dinic.add_edge(0, 2, 5)    dinic.add_edge(1, 2, 5)    dinic.add_edge(1, 3, 10)    dinic.add_edge(2, 3, 10)    print(dinic.max_flow(0, 3))  # 输出 15

1. self.adj[u].append([v, cap, len(self.adj[v])])建边时同时记录反向边在邻接表中的下标，这是后续更新反向容量的“钩子”
2. self.level[e[0]] = self.level[u] + 1BFS 给邻点分层，层号递增是 Dinic 保证路径单调向前的关键
3. if e[1] > 0 and self.level[u] + 1 == self.level[e[0]]:只在残余容量大于 0 且层号 +1 的边上走，绝不横跳或后退
4. self.it[u] += 1当前弧优化：这条边已经试过了，下次直接从下一条开始，避免重复检查饱和边
5. self.adj[e[0]][e[2]][1] += ret更新反向边容量，相当于给水流留出“反悔通道”
6. while self.bfs(s, t):每轮重新分层，直到汇点不可达说明最大流已求出
7. flow += f把每一轮阻塞流的总增量累加进最终答案

常见误区

面试题