引言：从运输问题到网络流
网络流问题是图论中最具实用价值的分支之一。想象一个原油管道系统：源点出发，经过多个中转站，最终抵达汇点，每条管道有容量上限。如何计算从源到汇的最大输送量？这正是最大流问题的核心。
Dinic算法由以色列计算机科学家Yefim Dinitz于1970年提出，是对Ford-Fulkerson方法的重大改进。它通过分层图（Level Graph）与阻塞流（Blocking Flow）两层优化，将时间复杂度从朴素的O(E·|f|)压缩到O(V²E)，在稠密图上表现尤为出色。本文将用Java完整实现Dinic算法，并讲解其核心思想。
核心概念：残量网络与增广路
在深入Dinic之前，先回顾两个基石概念：
残量网络（Residual Network）：对于每条边(u,v)及其流量f(u,v)，定义残量容量为c(u,v)−f(u,v)。同时引入反向边(v,u)，其残量容量为f(u,v)。反向边的意义在于允许算法”撤销”已分配的流量，从而发现更优路径。
增广路（Augmenting Path）：残量网络中从源点到汇点的一条路径，其上所有边的残量容量均大于0。沿增广路推送流量，即可增加总流量，直到残量网络中不再存在增广路——此时即达到最大流（最大流最小割定理保证）。
Dinic的核心洞察是：如果每次只找一条增广路，反复BFS/DFS的效率太低。它通过分层图一次性找到多条不相交的增广路，批量推送流量。
分层图与阻塞流
分层图：以源点为起点，通过BFS为每个顶点标记层级（level），仅保留从层级i指向层级i+1的边。这保证了图中不存在回头路，所有从源到汇的路径长度严格递增。
阻塞流：在分层图中，若从源到汇的每一条路径上都至少有一条边被”饱和”（残量为0），则当前流称为阻塞流。此时无法在分层图中继续增广，需要重新BFS构建新的分层图。
Dinic算法的框架由此清晰：
1. BFS构建分层图，若汇点不可达则终止。
2. 在分层图中用DFS寻找阻塞流，允许多路增广。
3. 重复步骤1-2直到不存在增广路。
Java完整实现
以下项目包含Dinic算法核心、边类定义、多路增广DFS以及一个经典的二分图匹配转化案例。
import java.util.*;
/**
* Dinic最大流算法实现
* 核心思想：BFS分层图 + DFS多路增广阻塞流
* 时间复杂度：O(V^2 * E)，在二分图匹配等场景下可优化至O(E * sqrt(V))
*/
public class DinicMaxFlow {
/**
* 边类：使用链式前向星思想，但为可读性采用邻接表+Edge对象实现
* 每条逻辑边对应一条正向边和一条反向边
*/
static class Edge {
int to; // 目标顶点
long cap; // 残量容量
int rev; // 反向边在邻接表中的索引
Edge(int to, long cap, int rev) {
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
private final int n; // 顶点数
private final List<Edge>[] graph; // 邻接表
private final int[] level; // BFS分层层级
private final int[] iter; // DFS当前弧优化：记录每条边遍历到何处
@SuppressWarnings("unchecked")
public DinicMaxFlow(int n) {
this.n = n;
this.graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
this.level = new int[n];
this.iter = new int[n];
}
/**
* 添加带容量限制的边，同时自动创建反向边（初始容量为0）
* @param from 起点
* @param to 终点
* @param cap 容量
*/
public void addEdge(int from, int to, long cap) {
// 正向边：索引为 graph[to].size() 的反向边
graph[from].add(new Edge(to, cap, graph[to].size()));
// 反向边：索引为 graph[from].size() - 1 的反向边
graph[to].add(new Edge(from, 0, graph[from].size() - 1));
}
/**
* BFS构建分层图
* 从源点s出发，计算每个顶点的最短距离（按边数）
* @param s 源点
* @param t 汇点
* @return 汇点是否可达
*/
private boolean bfs(int s, int t) {
Arrays.fill(level, -1);
Queue<Integer> queue = new LinkedList<>();
level[s] = 0;
queue.offer(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (Edge e : graph[v]) {
// 只走残量大于0的边，且未访问的顶点
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
queue.offer(e.to);
}
}
}
return level[t] >= 0;
}
/**
* DFS在分层图中寻找增广路
* 当前弧优化：iter[v] 记录v的邻接表遍历进度，避免重复检查已失效的边
* @param v 当前顶点
* @param t 汇点
* @param f 当前路径上的最小残量（初始为无穷大）
* @return 实际推送的流量
*/
private long dfs(int v, int t, long f) {
if (v == t) {
return f; // 抵达汇点，返回这条路径能推送的流量
}
// 从iter[v]开始遍历，跳过之前已经检查过且无法再增广的边
for (int i = iter[v]; i < graph[v].size(); i++) {
Edge e = graph[v].get(i);
if (e.cap > 0 && level[v] < level[e.to]) {
long d = dfs(e.to, t, Math.min(f, e.cap));
if (d > 0) {
// 推送流量：正向边减少，反向边增加
e.cap -= d;
graph[e.to].get(e.rev).cap += d;
return d;
}
}
iter[v]++; // 当前边无法增广，推进当前弧指针
}
return 0; // 无增广路
}
/**
* 多路增广DFS：一次性从v推送尽可能多的流量
* 这是Dinic的关键优化，相比单路增广能显著提升效率
*/
private long dfsMulti(int v, int t, long f) {
if (v == t) {
return f;
}
long totalPushed = 0;
for (int i = iter[v]; i < graph[v].size() && f > 0; i++) {
Edge e = graph[v].get(i);
if (e.cap > 0 && level[v] < level[e.to]) {
long d = dfsMulti(e.to, t, Math.min(f, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to].get(e.rev).cap += d;
f -= d;
totalPushed += d;
} else {
iter[v]++;
}
} else {
iter[v]++;
}
}
return totalPushed;
}
/**
* 计算从s到t的最大流
* 外层循环：反复BFS建分层图
* 内层循环：在分层图中DFS寻找阻塞流
*/
public long maxFlow(int s, int t) {
long flow = 0;
final long INF = Long.MAX_VALUE / 4; // 防止溢出的大数
while (bfs(s, t)) {
Arrays.fill(iter, 0); // 重置当前弧
long f;
// 不断寻找增广路，直到分层图中不存在增广路（即形成阻塞流）
while ((f = dfsMulti(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
// ==================== 应用案例：二分图最大匹配 ====================
/**
* 二分图最大匹配的网络流转化
* 建图方式：源点 -> 左部顶点 -> 右部顶点 -> 汇点
* 所有边容量设为1，最大流即为最大匹配数
*/
public static int bipartiteMatching(int leftCount, int rightCount, int[][] edges) {
// 顶点编号：源点=0，左部[1, leftCount]，右部[leftCount+1, leftCount+rightCount]，汇点=last
int s = 0;
int offsetLeft = 1;
int offsetRight = offsetLeft + leftCount;
int t = offsetRight + rightCount;
DinicMaxFlow dinic = new DinicMaxFlow(t + 1);
// 源点到左部
for (int i = 0; i < leftCount; i++) {
dinic.addEdge(s, offsetLeft + i, 1);
}
// 左部到右部的边
for (int[] e : edges) {
int u = e[0]; // 左部索引（0-based）
int v = e[1]; // 右部索引（0-based）
dinic.addEdge(offsetLeft + u, offsetRight + v, 1);
}
// 右部到汇点
for (int i = 0; i < rightCount; i++) {
dinic.addEdge(offsetRight + i, t, 1);
}
return (int) dinic.maxFlow(s, t);
}
// ==================== 主程序与测试 ====================
public static void main(String[] args) {
System.out.println("===== 示例1：基础网络流 =====");
// 经典示例：0为源点，5为汇点
// 0 -> 1(cap=10), 0 -> 2(cap=10)
// 1 -> 2(cap=2), 1 -> 3(cap=4), 1 -> 4(cap=8)
// 2 -> 4(cap=9)
// 3 -> 5(cap=10)
// 4 -> 3(cap=6), 4 -> 5(cap=10)
DinicMaxFlow dinic1 = new DinicMaxFlow(6);
dinic1.addEdge(0, 1, 10);
dinic1.addEdge(0, 2, 10);
dinic1.addEdge(1, 2, 2);
dinic1.addEdge(1, 3, 4);
dinic1.addEdge(1, 4, 8);
dinic1.addEdge(2, 4, 9);
dinic1.addEdge(3, 5, 10);
dinic1.addEdge(4, 3, 6);
dinic1.addEdge(4, 5, 10);
long flow1 = dinic1.maxFlow(0, 5);
System.out.println("最大流: " + flow1 + " (预期: 19)");
System.out.println("\n===== 示例2：二分图最大匹配 =====");
// 左部3人，右部3个工作，边的关系如下
int[][] matchEdges = {
{0, 0}, {0, 1},
{1, 0}, {1, 2},
{2, 1}, {2, 2}
};
int match = bipartiteMatching(3, 3, matchEdges);
System.out.println("最大匹配数: " + match + " (预期: 3)");
System.out.println("\n===== 示例3：大规模压力测试 =====");
int scale = 1000;
DinicMaxFlow dinic3 = new DinicMaxFlow(scale + 2);
int source = 0, sink = scale + 1;
Random rand = new Random(42);
long edgeCount = 0;
for (int i = 1; i <= scale; i++) {
dinic3.addEdge(source, i, rand.nextInt(100) + 1);
dinic3.addEdge(i, sink, rand.nextInt(100) + 1);
edgeCount += 2;
// 随机添加中间层边
if (i < scale) {
int extra = rand.nextInt(3);
for (int k = 0; k < extra; k++) {
int to = rand.nextInt(scale - i) + i + 1;
dinic3.addEdge(i, to, rand.nextInt(50) + 1);
edgeCount++;
}
}
}
long start = System.nanoTime();
long flow3 = dinic3.maxFlow(source, sink);
long elapsed = System.nanoTime() - start;
System.out.printf("顶点数: %d, 边数: %d%n", scale + 2, edgeCount);
System.out.printf("最大流: %d, 耗时: %.3f ms%n", flow3, elapsed / 1_000_000.0);
System.out.println("\n===== 示例4：多源多汇转化 =====");
// 多源多汇问题可通过超级源点和超级汇点转化为单源单汇
DinicMaxFlow dinic4 = new DinicMaxFlow(8);
int superS = 6, superT = 7;
// 原源点0,1连接到超级源点
dinic4.addEdge(superS, 0, 5);
dinic4.addEdge(superS, 1, 3);
// 原网络
dinic4.addEdge(0, 2, 4);
dinic4.addEdge(0, 3, 2);
dinic4.addEdge(1, 3, 3);
dinic4.addEdge(2, 4, 3);
dinic4.addEdge(3, 4, 2);
dinic4.addEdge(3, 5, 4);
dinic4.addEdge(4, superT, 5);
dinic4.addEdge(5, superT, 6);
long flow4 = dinic4.maxFlow(superS, superT);
System.out.println("多源多汇最大流: " + flow4 + " (预期: 8)");
}
}
关键优化详解
当前弧优化（Current Arc Optimization）
在分层图中，一条边一旦被饱和（cap降为0），在当前分层图内就再也无法用于增广。如果每次DFS都从头扫描邻接表，会浪费大量时间。iter[v]数组记录顶点v的邻接表已检查到的位置，下次直接从该位置继续，将DFS的均摊复杂度控制在O(E)每轮分层图。
多路增广（Multi-path Augmentation）
单路DFS每次只找到一条增广路就返回，而多路增广dfsMulti会尝试从当前顶点向多个分支同时推送流量，将一条路径上能分配的所有流量”榨干”后再返回。这使得每轮分层图内可以一次性完成多次增广，显著减少BFS次数。
复杂度分析
| 指标 | 普通Ford-Fulkerson | Edmonds-Karp | Dinic |
|---|---|---|---|
| 时间复杂度 | O(E·|f|) | O(V·E²) | O(V²·E) |
| 适用范围 | 整数容量 | 任意有理容量 | 任意有理容量 |
| 单位网络 | — | — | O(E·√V) |
在二分图匹配这类单位网络（所有边容量为1）中，Dinic的时间复杂度可进一步降至O(E·√V)，与Hopcroft-Karp算法同阶，表现极为出色。
扩展与变体
最小费用最大流（MCMF）
在实际工程中，最大流往往只是约束条件，真正的目标是在满足最大流的前提下使总费用最小。将Dinic的BFS替换为SPFA或Dijkstra（处理势能），即可得到最小费用最大流算法，广泛用于物流调度、任务分配等场景。
上下界网络流
某些场景下，边不仅有容量上限，还有流量下限。通过引入虚拟源汇点和可行流预处理，可将上下界问题转化为标准最大流问题求解。
多源多汇网络流
如代码示例4所示，通过添加超级源点（连接所有真实源点，容量无穷或各自供给量）和超级汇点（连接所有真实汇点），即可将多源多汇问题标准化为单源单汇问题。
总结
Dinic算法通过分层图和阻塞流的两层架构，优雅地解决了最大流问题。本文你掌握了：
- 残量网络与增广路的数学基础
- BFS分层图与DFS多路增广的协同机制
- 当前弧优化等工程实现技巧
- 完整的Java代码，涵盖建图、核心算法与二分图匹配转化
- 时间复杂度分析与单位网络的性能优势
网络流算法的思想深远影响着现代计算机科学的诸多领域，从编译器优化到交通规划，从图像分割到推荐系统。掌握Dinic算法，不仅是图论学习的重要里程碑，更为理解更复杂的网络优化问题奠定了坚实基础。
