Difference Constraints

function solveDifferenceConstraints(n, constraints) {
    // constraints: [{i, j, w}] meaning x[j] - x[i] <= w
    // Returns feasible x[] or null if infeasible
    const INF = Infinity;
    const dist = new Array(n + 1).fill(INF);
    const src = n; // virtual source node
    dist[src] = 0;

    const edges = [];
    for (const {i, j, w} of constraints) edges.push([i, j, w]);
    // Add edges from virtual source to all nodes (x[i] - src ≤ 0 → x[i] ≤ 0)
    for (let i = 0; i < n; i++) edges.push([src, i, 0]);

    // Bellman-Ford: n+1 nodes, n iterations
    for (let iter = 0; iter < n; iter++) {
        for (const [u, v, w] of edges) {
            if (dist[u] < INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    // Check for negative cycles
    for (const [u, v, w] of edges) {
        if (dist[u] < INF && dist[u] + w < dist[v]) return null; // infeasible
    }
    return dist.slice(0, n); // x[i] = dist[i] is a feasible solution
}

// Key insight: x[j] - x[i] <= w is the triangle inequality on the path i → j
// If dist[j] ≤ dist[i] + w (shortest path property), constraint is satisfied