算法概述
最高标号预流推进算法（Highest Label Preflow-Push，简称HLPP）是求解网络最大流问题的高效算法，由Goldberg和Tarjan提出。与Edmonds-Karp的增广路思想和Dinic的分层图阻塞流不同，HLPP采用”预流”概念：允许节点在计算过程中暂时拥有超出流出量的流入量（称为盈余），通过不断将盈余向汇点推送，最终使所有中间节点盈余为零，此时预流即转化为合法的最大流。
核心原理
HLPP的核心机制包含三个关键概念：
-
高度函数（Height/Label）：每个节点被赋予一个高度值，预流只能从高节点推送到低节点（高度差至少为1）。汇点高度固定为0，源点高度初始为节点数。
-
预流推送（Push）：对于存在盈余的节点，若存在邻接边允许推送（仍有残余容量且终点高度低1），则将尽可能多的流推送过去。
-
重标号（Relabel）：当节点有盈余但无法向任何邻居推送时，将其高度提升为所有可到达邻居的最小高度加1，以创造新的推送机会。
最高标号策略：每次优先处理高度最高的盈余节点，使得流尽可能快地接近汇点。
间隙启发式（Gap Heuristic）：若某高度值没有节点占据（出现”间隙”），则所有高于该间隙的节点不可能再有流到达汇点，可直接将其高度提升至n+1以上，加速算法收敛。
Java完整实现
import java.util.*;
/**
* HLPP（最高标号预流推进）最大流算法实现
* 时间复杂度：O(V²·√E) 实际表现接近 O(V³)
* 适用场景：稠密图、复杂网络流建模
*/
public class HLPPMaxFlow {
// 边类
static class Edge {
int to, rev; // 终点、反向边索引
long cap; // 残余容量
Edge(int to, long cap, int rev) {
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
private int n; // 节点数
private int source, sink; // 源点、汇点
private List<Edge>[] graph; // 邻接表
private long[] excess; // 每个节点的盈余
private int[] height; // 高度标号
private int[] count; // 各高度的节点数（间隙启发式用）
private List<Integer>[] buckets; // 按高度分桶的活跃节点
private int maxHeight; // 当前最大高度
@SuppressWarnings("unchecked")
public HLPPMaxFlow(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.excess = new long[n];
this.height = new int[n];
this.count = new int[2 * n + 1];
this.buckets = new ArrayList[2 * n + 1];
for (int i = 0; i < buckets.length; i++) buckets[i] = new ArrayList<>();
this.maxHeight = 0;
}
/**
* 添加有向边
*/
public void addEdge(int from, int to, long capacity) {
Edge forward = new Edge(to, capacity, graph[to].size());
Edge backward = new Edge(from, 0, graph[from].size());
graph[from].add(forward);
graph[to].add(backward);
}
/**
* 从u向v推送流量
*/
private void push(int u, Edge edge) {
int v = edge.to;
long delta = Math.min(excess[u], edge.cap);
if (delta == 0 || height[u] != height[v] + 1) return;
edge.cap -= delta;
graph[v].get(edge.rev).cap += delta;
excess[u] -= delta;
excess[v] += delta;
// 将v加入活跃节点桶
if (v != source && v != sink && excess[v] == delta) {
buckets[height[v]].add(v);
maxHeight = Math.max(maxHeight, height[v]);
}
}
/**
* 重标号节点u
*/
private void relabel(int u) {
int minHeight = Integer.MAX_VALUE;
for (Edge e : graph[u]) {
if (e.cap > 0) {
minHeight = Math.min(minHeight, height[e.to]);
}
}
if (minHeight < Integer.MAX_VALUE) {
count[height[u]]--; // 间隙启发式：原高度计数减1
height[u] = minHeight + 1; // 新高度
count[height[u]]++; // 新高度计数加1
maxHeight = Math.max(maxHeight, height[u]);
}
}
/**
* 间隙启发式：当某高度没有节点时，高于该高度的节点无法再推送流至汇点
*/
private void gapHeuristic(int emptyHeight) {
for (int u = 0; u < n; u++) {
if (u != source && height[u] > emptyHeight && height[u] <= n) {
count[height[u]]--;
height[u] = Math.max(height[u], n + 1);
count[height[u]]++;
}
}
}
/**
* 从源点进行初始推送（BFS设置高度后）
*/
private void initialize() {
// BFS从汇点反向设置初始高度
Arrays.fill(height, n); // 默认高度为n（不可达）
height[sink] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(sink);
while (!queue.isEmpty()) {
int u = queue.poll();
for (Edge e : graph[u]) {
int v = e.to;
// 反向边有容量表示原边有流量，即v可以到达u
Edge rev = graph[v].get(e.rev);
if (rev.cap > 0 && height[v] == n) {
height[v] = height[u] + 1;
queue.add(v);
}
}
}
height[source] = n; // 源点高度设为n
// 统计各高度节点数
for (int i = 0; i < n; i++) {
if (height[i] <= n) {
count[height[i]]++;
}
}
// 从源点推送初始流量
for (Edge e : graph[source]) {
if (e.cap > 0) {
long delta = e.cap;
e.cap = 0;
graph[e.to].get(e.rev).cap += delta;
excess[source] -= delta;
excess[e.to] += delta;
if (e.to != sink) {
buckets[height[e.to]].add(e.to);
maxHeight = Math.max(maxHeight, height[e.to]);
}
}
}
}
/**
* 执行HLPP算法计算最大流
*/
public long maxFlow() {
initialize();
// 处理活跃节点（最高标号优先）
while (maxHeight > 0) {
List<Integer> bucket = buckets[maxHeight];
while (!bucket.isEmpty()) {
int u = bucket.remove(bucket.size() - 1);
if (excess[u] == 0) continue;
boolean pushed = false;
for (Edge e : graph[u]) {
if (e.cap > 0 && height[u] == height[e.to] + 1) {
push(u, e);
pushed = true;
if (excess[u] == 0) break;
}
}
if (excess[u] > 0) {
if (!pushed) {
int oldHeight = height[u];
relabel(u);
// 间隙启发式检查
if (oldHeight > 0 && oldHeight <= n && count[oldHeight] == 0) {
gapHeuristic(oldHeight);
}
}
if (height[u] < buckets.length) {
buckets[height[u]].add(u);
maxHeight = Math.max(maxHeight, height[u]);
}
}
}
maxHeight--;
}
return excess[sink];
}
/**
* 获取最小割中源点侧的节点集合
*/
public List<Integer> getMinCutSourceSide() {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.add(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.add(e.to);
}
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (visited[i]) result.add(i);
}
return result;
}
public static void main(String[] args) {
// 测试经典案例
HLPPMaxFlow hlpp = new HLPPMaxFlow(6, 0, 5);
hlpp.addEdge(0, 1, 16);
hlpp.addEdge(0, 2, 13);
hlpp.addEdge(1, 2, 10);
hlpp.addEdge(1, 3, 12);
hlpp.addEdge(2, 1, 4);
hlpp.addEdge(2, 4, 14);
hlpp.addEdge(3, 2, 9);
hlpp.addEdge(3, 5, 20);
hlpp.addEdge(4, 3, 7);
hlpp.addEdge(4, 5, 4);
long maxFlow = hlpp.maxFlow();
System.out.println("最大流: " + maxFlow); // 期望 23
System.out.println("源点侧最小割: " + hlpp.getMinCutSourceSide());
// 二分图匹配测试
HLPPMaxFlow bipartite = new HLPPMaxFlow(8, 0, 7);
// 左侧节点 1-3, 右侧节点 4-6
bipartite.addEdge(0, 1, 1);
bipartite.addEdge(0, 2, 1);
bipartite.addEdge(0, 3, 1);
bipartite.addEdge(1, 4, 1);
bipartite.addEdge(1, 5, 1);
bipartite.addEdge(2, 4, 1);
bipartite.addEdge(2, 6, 1);
bipartite.addEdge(3, 5, 1);
bipartite.addEdge(4, 7, 1);
bipartite.addEdge(5, 7, 1);
bipartite.addEdge(6, 7, 1);
System.out.println("\n二分图最大匹配: " + bipartite.maxFlow()); // 期望 3
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V²·√E) | 理论界，实际接近 O(V³) |
| 实际性能 | O(V·E) ~ O(V³) | 在稠密图上优于Dinic |
| 空间复杂度 | O(V + E) | 邻接表存储 |
| 非饱和推送 | O(V²·E) | 每次推送至少使一个节点高度增加 |
| 重标号次数 | O(V²) | 每个节点最多重标号V次 |
应用场景
- 二分图最大匹配：通过拆点建流网络求解
- 多源多汇网络：超级源汇建模
- 最小割问题：最大流最小割定理的直接应用
- 图像分割：GrabCut等算法的图割能量最小化
- 交通网络：道路通行能力规划与瓶颈分析
HLPP算法在稠密图和复杂网络流模型中展现出比Dinic更稳定的性能表现，是竞赛和工程中的高阶选择。
