最大流与最小割算法：Dinic 算法详解
Dinic 算法是目前工程中最常用的高效最大流算法，由以色列数学家 Yefim Dinitz 于 1970 年提出。它在 Edmonds-Karp 算法的基础上做了两大核心优化：
- 分层图构建：用 BFS 为残量网络的顶点按到源点的最短距离（边数）分层，保证只在层间单向流动（仅允许从第 k 层流向第 k+1 层）；
- 阻塞流查找：用 DFS 在分层图中查找阻塞流（分层图中不存在增广路径时的流），一次 DFS 可批量找到多条增广路径，大幅减少迭代次数。
Dinic 算法的时间复杂度为 O(V²E)（V 为顶点数，E 为边数），在实际应用中（尤其是二分图等特殊图）效率远超 Edmonds-Karp。
一、核心概念
| 概念 | 定义 |
|---|---|
| 分层图 | 对残量网络做 BFS，给每个顶点标记层次（到源点的最短边数），仅保留 u 到 v 且 level[v]=level[u]+1 的边，形成的有向无环图。 |
| 阻塞流 | 分层图中无法再找到增广路径时的流，即分层图的'饱和流'，一次阻塞流可包含多条增广路径。 |
| 当前弧优化 | DFS 查找阻塞流时，记录每个顶点的当前遍历到的边索引，避免重复遍历无效边，进一步提升效率。 |
二、算法核心原理
- 分层图是基础：分层保证了增广路径的最短性，且分层图是有向无环图，无环的特性让 DFS 查找阻塞流时不会陷入循环；
- 阻塞流批量增广：一次 DFS 可在分层图中找到多条增广路径，将这些路径的流量一次性更新，比 Edmonds-Karp 的'一条路径一次更新'效率更高；
- 迭代终止条件：当 BFS 无法给汇点分层（即残量网络中不存在源点到汇点的路径）时，当前流即为最大流。
三、算法步骤
Dinic 算法的执行流程分为 分层 → 找阻塞流 → 更新残量网络 三步循环，直到无法分层为止：
- 步骤 1：BFS 构建分层图
- 初始化顶点层次
level[]为 -1（未访问），源点层次level[s] = 0； - 用 BFS 遍历残量网络，仅访问残量容量 >0 的边，给每个可达顶点标记层次（level[v]=level[u]+1）；
- 若汇点 t 无法被分层（level[t]=-1），算法终止，当前总流量即为最大流。
- 初始化顶点层次
- 步骤 2：DFS 查找阻塞流（带当前弧优化）
- 初始化当前弧索引
ptr[]为 0（记录每个顶点的当前遍历边）； - 从源点 s 出发，在分层图中 DFS：仅遍历 level[v]=level[u]+1 且残量 >0 的边；
- 递归计算从当前顶点 u 到汇点 t 的可增广流量，若 u=t 则返回当前流量，否则取所有邻边的可增广流量的最小值；
- 更新当前边的残量容量和反向边的残量容量，同时更新当前弧索引（跳过已饱和的边）。
- 初始化当前弧索引
- 步骤 3：累加阻塞流流量
- 将找到的阻塞流流量累加到总最大流中；
- 重复步骤 1-2，直到 BFS 无法分层为止。
四、完整代码实现（Python，带当前弧优化）
from collections import deque
class Dinic:
def __init__(self, n, source, sink):
""" 初始化 Dinic 算法
:param n: 顶点总数（0~n-1）
:param source: 源点编号
:param sink: 汇点编号
"""
self.n = n
self.source = source
self.sink = sink
# 邻接表结构：graph[u] = [(v, capacity, reverse_edge_index), ...]
self.graph = [[] for _ in range(n)]
# 层次数组：记录顶点的分层
self.level = [-1] * n
# 当前弧数组：记录每个顶点的当前遍历边索引，优化 DFS
self.ptr = [0] * n
def add_edge(self, u, v, capacity):
""" 添加有向边 u->v，同时添加反向边 v->u（初始容量 0）
:param u: 起点
:param v: 终点
:param capacity: 边的容量
"""
# 正向边：目标 v，容量 capacity，反向边在 graph[v] 中的索引
forward = (v, capacity, len(self.graph[v]))
# 反向边：目标 u，容量 0，正向边在 graph[u] 中的索引
backward = (u, 0, len(self.graph[u]))
self.graph[u].append(forward)
self.graph[v].append(backward)
def bfs_level(self):
""" BFS 构建分层图，返回是否能到达汇点
分层规则：level[v] = level[u] + 1，仅残量容量>0 的边参与分层
"""
self.level = [-1] * self.n
q = deque()
# 源点层次为 0
self.level[self.source] = 0
q.append(self.source)
while q:
u = q.popleft()
for (v, cap, _) in self.graph[u]:
# 仅访问未分层且残量>0 的边
if self.level[v] == -1 and cap > 0:
self.level[v] = self.level[u] + 1
q.append(v)
# 提前终止：找到汇点即可停止 BFS
if v == self.sink:
return True
# 汇点不可达，返回 False
return self.level[self.sink] != -1
def dfs_flow(self, u, flow_limit):
""" DFS 查找阻塞流，返回从 u 到 sink 的可增广流量
:param u: 当前顶点
:param flow_limit: 当前路径的流量上限（瓶颈容量）
:return: 可增广的流量
"""
if u == self.sink:
return flow_limit
# 遍历从当前弧开始的边，避免重复遍历无效边
while self.ptr[u] < len(self.graph[u]):
edge_idx = self.ptr[u]
v, cap, rev_idx = self.graph[u][edge_idx]
# 仅访问下一层且残量>0 的边
if self.level[v] == self.level[u] + 1 and cap > 0:
# 递归查找子路径的瓶颈流量
min_flow = min(flow_limit, cap)
aug_flow = self.dfs_flow(v, min_flow)
if aug_flow > 0:
# 更新正向边残量
self.graph[u][edge_idx] = (v, cap - aug_flow, rev_idx)
# 更新反向边残量
rev_v, rev_cap, rev_rev_idx = self.graph[v][rev_idx]
self.graph[v][rev_idx] = (rev_v, rev_cap + aug_flow, rev_rev_idx)
return aug_flow
# 当前边无增广能力，移动到下一条边
self.ptr[u] += 1
# 无增广路径，返回 0
return 0
def max_flow(self):
""" 计算最大流"""
total_flow = 0
# 循环分层 + 找阻塞流
while self.bfs_level():
# 每次分层后，重置当前弧索引
self.ptr = [0] * self.n
# 不断查找阻塞流，直到无增广路径
while True:
flow = self.dfs_flow(self.source, float('inf'))
if flow == 0:
break
total_flow += flow
return total_flow
def min_cut(self):
""" 求解最小割：返回 (S 集合，T 集合，最小割容量)
注意：必须在调用 max_flow() 之后调用
"""
# BFS 标记残量网络中源点可达的顶点（S 集合）
visited = [False] * self.n
q = deque()
q.append(self.source)
visited[self.source] = True
while q:
u = q.popleft()
for (v, cap, _) in self.graph[u]:
if not visited[v] and cap > 0:
visited[v] = True
q.append(v)
S = [i for i in range(self.n) if visited[i]]
T = [i for i in range(self.n) if not visited[i]]
# 计算最小割容量：所有 S→T 的原边容量之和
cut_capacity = 0
for u in S:
for (v, cap, rev_idx) in self.graph[u]:
if v in T:
# 原边容量 = 正向边残量 + 反向边残量
rev_cap = self.graph[v][rev_idx][1]
cut_capacity += (cap + rev_cap)
return S, T, cut_capacity
# ==================== 测试示例 ====================
if __name__ == "__main__":
# 测试网络：4 顶点，源点 0，汇点 3
# 边结构：0→1(3), 0→2(2), 1→2(1), 1→3(2), 2→3(3)
n = 4
source = 0
sink = 3
dinic = Dinic(n, source, sink)
dinic.add_edge(0, 1, 3)
dinic.add_edge(0, 2, 2)
dinic.add_edge(1, 2, 1)
dinic.add_edge(1, 3, 2)
dinic.add_edge(2, 3, 3)
# 计算最大流
max_flow_val = dinic.max_flow()
print(f"最大流值：{max_flow_val}")
# 输出：5
# 计算最小割
S, T, cut_cap = dinic.min_cut()
print(f"最小割 S 集合：{S}")
print(f"最小割 T 集合：{T}")
print(f"最小割容量：{cut_cap}")
# 输出：5
五、算法核心优化点解析
- 分层图优化
- 保证每次增广的路径都是残量网络中的最短路径，避免了 DFS 陷入长路径的无效搜索；
- 分层图是有向无环图，DFS 查找阻塞流时不会出现环，无需额外的环检测。
- 当前弧优化
- 对每个顶点 u，记录当前遍历到的边索引
ptr[u]，已遍历过且无增广能力的边会被跳过； - 避免了重复遍历已饱和的边，将 DFS 的时间复杂度从 O(E) 优化到接近 O(V)。
- 对每个顶点 u，记录当前遍历到的边索引
六、算法性能分析
| 算法 | 时间复杂度 | 实际效率 | 适用场景 |
|---|---|---|---|
| Edmonds-Karp | O(VE²) | 较低 | 小规模网络（顶点数 < 500） |
| Dinic（带当前弧） | O(V²E) | 极高 | 中大规模网络（顶点数 < 10000） |
| ISAP（Dinic 优化版） | O(V²E) | 略高于 Dinic | 超大规模网络/竞赛常用 |
- Dinic 算法在二分图匹配等特殊场景下，时间复杂度可优化到 O(E√V)，效率远超其他算法；
- Python 实现的 Dinic 算法在顶点数 1000 以内的网络中，可轻松在毫秒级完成计算。
七、Dinic vs Edmonds-Karp 核心差异
| 特性 | Dinic 算法 | Edmonds-Karp 算法 |
|---|---|---|
| 增广路径查找 | 一次阻塞流包含多条增广路径 | 一次 BFS 仅找一条增广路径 |
| 迭代次数 | 少（分层次数为 O(V)） | 多（增广次数为 O(VE)） |
| 核心优化 | 分层图 + 当前弧 | 仅 BFS 最短路径 |
| 代码复杂度 | 中等 | 简单 |
| 大规模网络表现 | 优秀 | 较差 |
八、典型应用场景
- 二分图最大匹配/最大权匹配：将二分图转化为流网络，Dinic 算法是求解此类问题的最优选择之一；
- 多源多汇最大流：添加超级源点和超级汇点，转化为单源单汇问题；
- 带上下界的流网络：通过构造附加流网络，可快速求解可行流和最大流；
- 网络流的扩展问题：如最小费用最大流（在 Dinic 基础上增加费用计算）。
九、常见注意事项
- 反向边的维护：反向边的索引必须准确，否则会导致残量网络更新错误，这是所有网络流算法的核心易错点；
- 顶点编号连续性：确保顶点编号为 0∼n−1 的连续整数，避免数组越界；
- 无向边处理：将无向边拆分为两条方向相反的有向边，容量均为原边容量；
- 当前弧重置：每次 BFS 分层后，必须重置
ptr数组为 0，否则会导致 DFS 跳过有效边。