问题背景
差分约束系统（Difference Constraints）是一类特殊的不等式组，每个不等式的形式为 x_i - x_j ≤ c_k。这类系统可以高效地判定是否有解，并在有解时求出一组可行赋值。其核心思想是将不等式转化为图论中的最短路问题，利用Bellman-Ford或SPFA算法求解。
差分约束广泛应用于项目进度规划、资源分配、时序约束验证等实际场景。例如，任务A必须在任务B开始前完成，可以建模为 start_B - finish_A ≥ 0，转化为差分约束的标准形式。
核心算法思想
不等式转图论模型
对于约束 x_i - x_j ≤ c，等价于 x_i ≤ x_j + c，对应图中的有向边 j → i，边权为 c。从源点出发求最短路，若图中不存在负环，则最短路径长度即为一组可行解。
为处理不连通情况，通常引入超级源点 S，向所有变量节点添加权值为0的边 S → x_i。
负环判定
差分约束系统无解的充要条件是图中存在负环。Bellman-Ford算法在 n-1 轮松弛后，若仍能松弛，则说明存在负环。SPFA算法通过统计每个节点的入队次数，若超过 n 次则说明存在负环。
Java完整实现
import java.util.*;
/**
* 差分约束系统求解器
* 使用SPFA算法检测负环并求解可行解
*/
public class DifferenceConstraints {
static class Edge {
int to; // 目标节点
int weight; // 边权（约束中的c值）
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
private int n; // 变量个数（不含超级源点）
private List<Edge>[] graph; // 邻接表
private static final int INF = Integer.MAX_VALUE / 2;
public DifferenceConstraints(int n) {
this.n = n;
// 节点0为超级源点，1~n为变量节点
this.graph = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
graph[i] = new ArrayList<>();
}
// 超级源点向所有变量连权值为0的边
for (int i = 1; i <= n; i++) {
graph[0].add(new Edge(i, 0));
}
}
/**
* 添加约束: x_u - x_v <= w
* 对应边 v -> u，权值为 w
* 注意：节点编号从1开始
*/
public void addConstraint(int u, int v, int w) {
// x_u <= x_v + w => v -> u, weight = w
graph[v].add(new Edge(u, w));
}
/**
* 添加约束: x_u - x_v >= w
* 转化为: x_v - x_u <= -w
*/
public void addGreaterOrEqual(int u, int v, int w) {
// x_u >= x_v + w => x_v <= x_u - w
graph[u].add(new Edge(v, -w));
}
/**
* 添加等式约束: x_u == x_v + w
* 拆分为两个不等式
*/
public void addEqual(int u, int v, int w) {
addConstraint(u, v, w); // x_u - x_v <= w
addGreaterOrEqual(u, v, w); // x_u - x_v >= w
}
/**
* SPFA算法求解最短路并检测负环
* @return 若存在负环返回null；否则返回各变量的可行解（节点1~n）
*/
public int[] solve() {
int totalNodes = n + 1;
int[] dist = new int[totalNodes];
int[] count = new int[totalNodes]; // 节点入队次数
boolean[] inQueue = new boolean[totalNodes];
Arrays.fill(dist, INF);
dist[0] = 0;
inQueue[0] = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
count[v]++;
// 若某节点入队超过n次，说明存在负环
if (count[v] > n) {
return null;
}
}
}
}
}
// 返回变量节点的解（去掉超级源点）
int[] result = new int[n];
System.arraycopy(dist, 1, result, 0, n);
return result;
}
/**
* 使用Bellman-Ford算法检测负环（更稳定但较慢）
*/
public int[] solveByBellmanFord() {
int totalNodes = n + 1;
int[] dist = new int[totalNodes];
Arrays.fill(dist, INF);
dist[0] = 0;
// 松弛n轮
for (int i = 0; i < n; i++) {
boolean updated = false;
for (int u = 0; u < totalNodes; u++) {
if (dist[u] == INF) continue;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
}
if (!updated) break;
}
// 第n+1轮检查是否还能松弛
for (int u = 0; u < totalNodes; u++) {
if (dist[u] == INF) continue;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
return null; // 存在负环
}
}
}
int[] result = new int[n];
System.arraycopy(dist, 1, result, 0, n);
return result;
}
public static void main(String[] args) {
// 示例：变量 x1, x2, x3
// 约束: x1 - x2 <= 3
// x2 - x3 <= -2
// x1 - x3 <= 4
DifferenceConstraints dc = new DifferenceConstraints(3);
dc.addConstraint(1, 2, 3); // x1 - x2 <= 3
dc.addConstraint(2, 3, -2); // x2 - x3 <= -2
dc.addConstraint(1, 3, 4); // x1 - x3 <= 4
int[] solution = dc.solve();
if (solution != null) {
System.out.println("可行解: ");
for (int i = 0; i < solution.length; i++) {
System.out.println("x" + (i + 1) + " = " + solution[i]);
}
} else {
System.out.println("约束系统无解（存在负环）");
}
// 不可满足示例：x1 - x2 <= 1, x2 - x1 <= -3
DifferenceConstraints dc2 = new DifferenceConstraints(2);
dc2.addConstraint(1, 2, 1); // x1 <= x2 + 1
dc2.addConstraint(2, 1, -3); // x2 <= x1 - 3 => x1 >= x2 + 3
int[] sol2 = dc2.solve();
System.out.println(sol2 == null ? "不可满足（预期结果）" : "可满足");
}
}
算法复杂度分析
- 建图时间：
O(m)，m为约束数量 - SPFA求解：平均
O(m)，最坏O(nm)（存在负环时） - Bellman-Ford求解：稳定
O(nm) - 负环检测：与最短路算法同时进行
- 总时间复杂度：
O(nm)（最坏情况） - 空间复杂度：
O(n + m)
实际应用案例
项目工期规划
设 x_i 为任务i的最早开始时间，若任务j依赖于任务i且需要耗时 d，则有 x_j ≥ x_i + d，即 x_i - x_j ≤ -d。
最大差值求解
要求 max(x_i - x_j) 在约束下的最大值，可二分答案 mid，检验 x_i - x_j ≤ mid 是否有解。
差分约束的精髓在于”不等式即边”的转化思想。一旦掌握这种建模方式，许多看似复杂的约束问题都能迎刃而解。
