一、ISAP 算法原理
ISAP（Improved Shortest Augmenting Path）是最大流问题的高效算法，由 Ahuja 和 Orlin 在 1990 年代提出。与 Dinic 算法的分层图+BFS多路增广不同，ISAP 采用距离标号（Distance Label）和允许弧（Admissible Arc）思想，通过一次 BFS 初始化后，在 DFS 增广过程中动态维护距离标号，配合间隙优化（Gap Heuristic）大幅提升实际运行效率。
核心概念：
– 距离标号 d[v]：节点 v 到汇点 t 的最短距离（在残量网络中）
– 允许弧：满足 d[u] == d[v] + 1 且有剩余容量的边 (u, v)
– 间隙优化：当发现某个距离值 k 没有任何节点拥有时，将所有距离大于 k 的节点标号设为 n，直接切断无效搜索路径
二、边结构与图表示
import java.util.*;
/**
* ISAP 最大流算法实现
* 支持距离标号、允许弧优化与间隙优化
*/
public class ISAPMaxFlow {
/**
* 边对象：包含反向边引用，便于残量更新
*/
static class Edge {
int to; // 目标节点
long cap; // 剩余容量
long flow; // 已流流量
Edge rev; // 反向边引用
Edge(int to, long cap) {
this.to = to;
this.cap = cap;
this.flow = 0;
}
}
private int n; // 节点数
private int source; // 源点
private int sink; // 汇点
private List<Edge>[] graph; // 邻接表
private int[] dist; // 距离标号
private int[] gap; // 间隙计数：gap[i] = 距离标号为 i 的节点数
private int[] current; // 当前弧优化指针
@SuppressWarnings("unchecked")
public ISAPMaxFlow(int n, int source, int sink) {
this.n = n;
this.source = source;
this.sink = sink;
this.graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
this.dist = new int[n];
this.gap = new int[n + 1];
this.current = new int[n];
}
/**
* 添加边（自动创建反向边）
* @param from 起点
* @param to 终点
* @param cap 容量
*/
public void addEdge(int from, int to, long cap) {
Edge forward = new Edge(to, cap);
Edge backward = new Edge(from, 0); // 反向边初始容量为0
forward.rev = backward;
backward.rev = forward;
graph[from].add(forward);
graph[to].add(backward);
}
三、初始化：反向 BFS 构建距离标号
/**
* 从汇点反向 BFS 初始化距离标号
* 这是 ISAP 与 Dinic 的关键区别：只需一次 BFS 初始化
*/
private void bfsInit() {
Arrays.fill(dist, -1);
Arrays.fill(gap, 0);
ArrayDeque<Integer> queue = new ArrayDeque<>();
dist[sink] = 0;
gap[0] = 1;
queue.offer(sink);
while (!queue.isEmpty()) {
int u = queue.poll();
for (Edge e : graph[u]) {
// 反向 BFS：沿着反向边有流量的边，或正向边的反向边
// 注意：在残量网络中，反向边 rev 的 cap > 0 意味着原边有流量可以退回
Edge rev = e.rev;
if (dist[e.to] == -1 && rev.cap > 0) {
dist[e.to] = dist[u] + 1;
gap[dist[e.to]]++;
queue.offer(e.to);
}
}
}
}
四、核心 DFS 增广与动态标号更新
/**
* DFS 增广：从 u 出发，最多推送 amount 流量
* @return 实际推送的流量
*/
private long dfs(int u, long amount) {
if (u == sink) {
return amount;
}
long pushed = 0;
// 当前弧优化：从 current[u] 开始遍历，跳过已饱和的弧
for (int i = current[u]; i < graph[u].size(); i++) {
current[u] = i;
Edge e = graph[u].get(i);
// 只允许走允许弧：dist[u] == dist[v] + 1
if (e.cap > 0 && dist[u] == dist[e.to] + 1) {
long flow = dfs(e.to, Math.min(amount - pushed, e.cap));
if (flow > 0) {
e.cap -= flow;
e.flow += flow;
e.rev.cap += flow;
e.rev.flow -= flow;
pushed += flow;
if (pushed == amount) {
return pushed;
}
}
}
}
// 无法推送：需要更新距离标号
// 如果当前节点还有出边，找最小的 dist[v] + 1
int minDist = n; // 最大可能距离为 n-1
for (Edge e : graph[u]) {
if (e.cap > 0) {
minDist = Math.min(minDist, dist[e.to] + 1);
}
}
// 间隙优化核心：如果当前距离值只有一个节点，触发间隙
gap[dist[u]]--;
if (gap[dist[u]] == 0) {
// 出现间隙：将源点到当前节点之间的所有节点距离设为 n（切断）
// 实际实现中更常见的做法是：一旦发现 gap[k]==0，所有 dist > k 的节点设为 n
for (int i = 0; i < n; i++) {
if (dist[i] > dist[u] && dist[i] < n) {
dist[i] = n;
}
}
}
dist[u] = minDist;
if (dist[u] < n) {
gap[dist[u]]++;
}
current[u] = 0; // 重置当前弧
return pushed;
}
五、ISAP 主算法与间隙优化完整版
/**
* 计算从源点到汇点的最大流
*/
public long maxFlow() {
bfsInit();
// 如果源点不可达汇点
if (dist[source] == -1) {
return 0;
}
long totalFlow = 0;
Arrays.fill(current, 0);
// 当源点距离标号小于 n 时继续增广
while (dist[source] < n) {
long flow = dfs(source, Long.MAX_VALUE);
totalFlow += flow;
}
return totalFlow;
}
/**
* 获取某条边的实际流量（通过反向边 flow 获取）
*/
public long getEdgeFlow(int from, int to) {
for (Edge e : graph[from]) {
if (e.to == to) {
return e.flow;
}
}
return 0;
}
/**
* 获取残量网络中某条边的剩余容量
*/
public long getEdgeCapacity(int from, int to) {
for (Edge e : graph[from]) {
if (e.to == to) {
return e.cap;
}
}
return 0;
}
六、经典建模示例
6.1 二分图最大匹配
/**
* 二分图最大匹配转网络流
* @param leftCount 左部节点数
* @param rightCount 右部节点数
* @param edges 边列表 [left, right]
* @return 最大匹配数
*/
public static int bipartiteMatching(int leftCount, int rightCount, int[][] edges) {
int n = leftCount + rightCount + 2;
int source = 0;
int sink = n - 1;
ISAPMaxFlow mf = new ISAPMaxFlow(n, source, sink);
// 源点到左部
for (int i = 1; i <= leftCount; i++) {
mf.addEdge(source, i, 1);
}
// 右部到汇点
for (int i = leftCount + 1; i <= leftCount + rightCount; i++) {
mf.addEdge(i, sink, 1);
}
// 二分图边
for (int[] e : edges) {
mf.addEdge(e[0] + 1, leftCount + 1 + e[1], 1);
}
return (int) mf.maxFlow();
}
6.2 多源多汇最大流
/**
* 多源多汇最大流：建立超级源点和超级汇点
*/
public static long multiSourceMultiSink(int n, int[][] sources, int[][] sinks, int[][] edges) {
int newN = n + 2;
int superSource = n;
int superSink = n + 1;
ISAPMaxFlow mf = new ISAPMaxFlow(newN, superSource, superSink);
for (int[] s : sources) {
mf.addEdge(superSource, s[0], s[1]);
}
for (int[] t : sinks) {
mf.addEdge(t[0], superSink, t[1]);
}
for (int[] e : edges) {
mf.addEdge(e[0], e[1], e[2]);
}
return mf.maxFlow();
}
七、最小割求解
/**
* 获取最大流后的源点可达集合（最小割的 S 集合）
*/
public boolean[] minCutS() {
boolean[] visited = new boolean[n];
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(source);
visited[source] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
for (Edge e : graph[u]) {
if (e.cap > 0 && !visited[e.to]) {
visited[e.to] = true;
queue.offer(e.to);
}
}
}
return visited;
}
/**
* 获取最小割的边（从 S 集合指向 T 集合的满流边）
*/
public List<int[]> getMinCutEdges() {
boolean[] sSet = minCutS();
List<int[]> cutEdges = new ArrayList<>();
for (int u = 0; u < n; u++) {
if (!sSet[u]) continue;
for (Edge e : graph[u]) {
// 只考虑原边（通过容量为0且反向边有流量来判断）
if (!sSet[e.to] && e.cap == 0 && e.rev.cap > 0) {
cutEdges.add(new int[]{u, e.to});
}
}
}
return cutEdges;
}
八、完整测试
public static void main(String[] args) {
// 测试1：经典最大流样例
System.out.println("=== 测试1：基础最大流 ===");
ISAPMaxFlow mf1 = new ISAPMaxFlow(6, 0, 5);
mf1.addEdge(0, 1, 16);
mf1.addEdge(0, 2, 13);
mf1.addEdge(1, 2, 10);
mf1.addEdge(1, 3, 12);
mf1.addEdge(2, 1, 4);
mf1.addEdge(2, 4, 14);
mf1.addEdge(3, 2, 9);
mf1.addEdge(3, 5, 20);
mf1.addEdge(4, 3, 7);
mf1.addEdge(4, 5, 4);
long flow1 = mf1.maxFlow();
System.out.println("最大流: " + flow1); // 应为 23
boolean[] cut = mf1.minCutS();
System.out.print("S 集合: ");
for (int i = 0; i < cut.length; i++) {
if (cut[i]) System.out.print(i + " ");
}
System.out.println();
// 测试2：二分图匹配
System.out.println("
=== 测试2：二分图最大匹配 ===");
int[][] edges = {{0, 0}, {0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 2}};
int match = bipartiteMatching(3, 3, edges);
System.out.println("最大匹配: " + match); // 应为 3
// 测试3：大规模随机图
System.out.println("
=== 测试3：性能测试 ===");
int n = 1000;
ISAPMaxFlow mf3 = new ISAPMaxFlow(n, 0, n - 1);
Random rand = new Random(42);
int m = 5000;
for (int i = 0; i < m; i++) {
int u = rand.nextInt(n - 2) + 1;
int v = rand.nextInt(n - 2) + 1;
long cap = rand.nextInt(1000) + 1;
mf3.addEdge(u, v, cap);
}
long start = System.currentTimeMillis();
long flow3 = mf3.maxFlow();
long time = System.currentTimeMillis() - start;
System.out.println("节点: " + n + ", 边: " + m);
System.out.println("最大流: " + flow3);
System.out.println("耗时: " + time + "ms");
}
}
九、复杂度分析与算法对比
| 算法 | 时间复杂度 | 空间复杂度 | BFS次数 | 实际性能 |
|---|---|---|---|---|
| Edmonds-Karp | O(V × E²) | O(V + E) | 每次增广 | 慢 |
| Dinic | O(V² × E) | O(V + E) | 多次分层 | 中 |
| ISAP | O(V² × E) | O(V + E) | 仅1次初始化 | 快 |
| Push-Relabel | O(V³) | O(V + E) | 无 | 快（稠密图） |
ISAP 的实际优势：
1. 仅需一次 BFS 初始化，后续通过动态标号更新维护层次
2. 间隙优化能大幅剪枝，实际运行常数远小于理论值
3. 当前弧优化避免重复遍历饱和边
4. 在稀疏图（如网络、运输问题）上通常比 Dinic 快 2-5 倍
ISAP 算法是网络流问题在工程实践中的首选算法之一，特别适合需要频繁求解最大流/最小割的场景，如图像分割、网络可靠性分析和任务调度优化。
