每日算法 — 使用java实现差分约束：最短路建模与系统可行性判定

差分约束系统（System of Difference Constraints）是一类特殊的不等式组，形如 xᵢ - xⱼ ≤ cₖ。这类系统可以巧妙地转化为图论中的单源最短路径问题求解，是算法竞赛和实际工程中判断约束系统可行性的重要工具。本文用Java完整实现差分约束系统的建模与求解。

一、问题引入：项目排期约束

假设有 n 个任务，任务之间存在如下约束：

• 任务A必须在任务B开始前完成：B_start - A_end ≥ 0
• 两个任务之间至少间隔3天：B_start - A_end ≥ 3
• 任务C必须在任务D开始后5天内启动：C_start - D_start ≤ 5

将这些约束统一变形为 xⱼ - xᵢ ≤ c 的形式，就构成了差分约束系统。

二、核心定理：差分约束转最短路

定理：差分约束系统 xⱼ - xᵢ ≤ cₖ 有解，当且仅当对应的图中不存在负权环。

建图方法：
– 对每个变量 xᵢ，创建节点 i
– 对每条约束 xⱼ - xᵢ ≤ c，添加有向边 i → j，权值为 c
– 添加超级源点 S，向所有节点连权值为0的边（保证图连通）

求解方法：从超级源点运行Bellman-Ford或SPFA算法求最短路。若 dist[j] 表示从源点到 j 的最短距离，则 xⱼ = dist[j] 就是一组可行解。

为什么有效？

最短路满足三角不等式：dist[j] ≤ dist[i] + w(i,j)，即 dist[j] - dist[i] ≤ w(i,j) = c，正好对应原约束。

三、完整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;

    /**
     * 初始化求解器
     * @param n 变量个数 (x₀ 到 xₙ₋₁)
     */
    @SuppressWarnings("unchecked")
    public DifferenceConstraints(int n) {
        this.n = n;
        // 节点0~n-1对应变量x₀~xₙ₋₁，节点n为超级源点
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    /**
     * 添加约束: x_j - x_i <= c
     * 对应边 i -> j，权值为 c
     * @param i 变量i的下标
     * @param j 变量j的下标
     * @param c 常数
     */
    public void addConstraint(int i, int j, int c) {
        graph[i].add(new Edge(j, c));
    }

    /**
     * 添加约束: x_j - x_i >= c
     * 变形为: x_i - x_j <= -c
     */
    public void addGreaterEqual(int i, int j, int c) {
        addConstraint(j, i, -c);
    }

    /**
     * 添加约束: x_j - x_i == c
     * 分解为: x_j - x_i <= c 且 x_i - x_j <= -c
     */
    public void addEqual(int i, int j, int c) {
        addConstraint(i, j, c);
        addConstraint(j, i, -c);
    }

    /**
     * 使用SPFA求解，返回可行解或检测负环
     * @return 若系统可行，返回各变量的一个解；若不可行，返回null
     */
    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[n] = 0; // 超级源点距离为0

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        inQueue[n] = true;

        // 超级源点向所有节点连权值为0的边
        for (int i = 0; i < n; i++) {
            graph[n].add(new Edge(i, 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;
                    count[v] = count[u] + 1;

                    // 若某节点入队超过n次，说明存在负环
                    if (count[v] >= totalNodes) {
                        return null; // 系统不可行
                    }

                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }

        // 返回x₀~xₙ₋₁的解（dist[0]~dist[n-1]）
        return Arrays.copyOf(dist, n);
    }

    /**
     * 求解并输出详细信息
     */
    public void solveWithInfo() {
        System.out.println("约束系统信息:");
        System.out.println("  变量个数: " + n);
        System.out.println("  约束条数: " + (graph[n].size() - n)); // 减去超级源点边
        for (int i = 0; i < n; i++) {
            for (Edge e : graph[i]) {
                System.out.printf("    x%d - x%d <= %d%n", e.to, i, e.weight);
            }
        }

        int[] solution = solve();
        if (solution == null) {
            System.out.println("\n结果: 系统不可行（存在矛盾约束/负环）");
        } else {
            System.out.println("\n结果: 系统可行，一组解为:");
            for (int i = 0; i < n; i++) {
                System.out.printf("  x%d = %d%n", i, solution[i]);
            }
        }
    }

    public static void main(String[] args) {
        // 示例1: 可行系统
        System.out.println("========== 示例1: 项目排期约束 ==========");
        DifferenceConstraints solver1 = new DifferenceConstraints(4);
        // x1 - x0 <= 5  (任务1在任务0开始后5天内开始)
        solver1.addConstraint(0, 1, 5);
        // x2 - x1 <= 3  (任务2在任务1开始后3天内开始)
        solver1.addConstraint(1, 2, 3);
        // x3 - x2 <= 2  (任务3在任务2开始后2天内开始)
        solver1.addConstraint(2, 3, 2);
        // x3 - x0 >= 8  -> x0 - x3 <= -8 (任务3至少在任务0开始8天后)
        solver1.addGreaterEqual(0, 3, 8);
        solver1.solveWithInfo();

        // 示例2: 不可行系统（存在矛盾）
        System.out.println("\n========== 示例2: 矛盾约束 ==========");
        DifferenceConstraints solver2 = new DifferenceConstraints(3);
        solver2.addConstraint(0, 1, 2);  // x1 - x0 <= 2
        solver2.addConstraint(1, 2, 3);  // x2 - x1 <= 3
        solver2.addConstraint(2, 0, -10); // x0 - x2 <= -10  => x2 - x0 >= 10
        // 链式推导: x2 - x0 <= 5, 但要求 >= 10，矛盾！
        solver2.solveWithInfo();

        // 示例3: 区间约束（常用于求解变量范围）
        System.out.println("\n========== 示例3: 区间范围约束 ==========");
        DifferenceConstraints solver3 = new DifferenceConstraints(3);
        // 0 <= x0 <= 10
        solver3.addConstraint(3, 0, 10);  // x0 <= 10 (使用虚拟节点3作为参考点，其值为0)
        // 实际实现中可以通过固定一个变量的值来求解相对范围
        // 更常见的方式: 求最大值时求最长路，求最小值时求最短路

        // 演示：求每个变量的最大值（转化为最长路）
        System.out.println("求解变量最大值（最长路）:");
        solveMaxValues();
    }

    /**
     * 求每个变量的最大可能值
     * 转化为最长路问题：x_j - x_i >= c  =>  边 i->j 权值为 c
     */
    private static void solveMaxValues() {
        // 对于求最大值，约束 x_j - x_i <= c 意味着 x_j 的上界
        // 最短路结果 dist[j] 就是 x_j 的最小上界（即最大值）
        DifferenceConstraints solver = new DifferenceConstraints(4);
        solver.addConstraint(0, 1, 5);
        solver.addConstraint(1, 2, 3);
        solver.addConstraint(0, 2, 10);

        int[] maxValues = solver.solve();
        if (maxValues != null) {
            System.out.println("各变量的一个可行解（也是最小值解）:");
            for (int i = 0; i < maxValues.length; i++) {
                System.out.printf("  x%d <= %d%n", i, maxValues[i]);
            }
        }
    }
}

四、高级应用：区间覆盖与变量范围

差分约束常用于求解”在已知相对约束下，某个变量的取值范围”。

/**
 * 差分约束高级应用：求解变量最大值和最小值
 */
public class RangeQueryWithConstraints {

    /**
     * 求每个变量的最大可能值
     * 方法: 以超级源点为起点求最短路，dist[i] 即为 x_i 的最大值
     */
    public static int[] maxValues(DifferenceConstraints solver) {
        return solver.solve();
    }

    /**
     * 求 x_target 的最大值和最小值
     * 最大值: 以超级源点为起点求最短路到 target
     * 最小值: 转化为求 -x_target 的最大值，即求最长路
     */
    public static void queryRange(List<int[]> constraints, int n, int target) {
        // 最大值: 直接求解原系统
        DifferenceConstraints maxSolver = new DifferenceConstraints(n);
        for (int[] c : constraints) {
            maxSolver.addConstraint(c[0], c[1], c[2]); // x_j - x_i <= c
        }
        int[] maxSolution = maxSolver.solve();
        int maxVal = maxSolution != null ? maxSolution[target] : Integer.MAX_VALUE;

        // 最小值: 将所有约束取反，x_i - x_j <= -c，求最短路
        DifferenceConstraints minSolver = new DifferenceConstraints(n);
        for (int[] c : constraints) {
            minSolver.addConstraint(c[1], c[0], -c[2]); // x_i - x_j <= -c
        }
        int[] minSolution = minSolver.solve();
        int minVal = minSolution != null ? -minSolution[target] : Integer.MIN_VALUE;

        System.out.printf("x%d 的取值范围: [%d, %d]%n", target, minVal, maxVal);
    }

    public static void main(String[] args) {
        List<int[]> constraints = new ArrayList<>();
        constraints.add(new int[]{0, 1, 5});  // x1 - x0 <= 5
        constraints.add(new int[]{1, 2, 3});  // x2 - x1 <= 3
        constraints.add(new int[]{0, 2, 10}); // x2 - x0 <= 10
        constraints.add(new int[]{2, 0, -4}); // x0 - x2 <= -4 => x2 - x0 >= 4

        System.out.println("约束条件:");
        for (int[] c : constraints) {
            System.out.printf("  x%d - x%d <= %d%n", c[1], c[0], c[2]);
        }

        for (int i = 0; i < 3; i++) {
            queryRange(constraints, 3, i);
        }
    }
}

五、建图技巧速查表

六、复杂度分析

其中 n 为变量数，m 为约束数。

七、总结

差分约束系统的精髓在于将代数不等式转化为图论最短路问题。这一转化的桥梁是三角不等式：dist[j] ≤ dist[i] + w(i,j)。掌握这一技巧后，你就能优雅地解决项目排期、资源分配、变量范围估计等一系列约束满足问题。记住核心口诀：”小于等于走最短路，大于等于反向建边走最长路”。