Pattern Guide
Difference Constraints
"x_j - x_i ≤ w → edge i→j with weight w. SSSP gives feasible solution."
A system of difference constraints (xⱼ - xᵢ ≤ wᵢⱼ) can be solved by shortest paths. Build a graph: for each constraint xⱼ - xᵢ ≤ w, add edge i → j with weight w. If no negative cycle: Bellman-Ford from a virtual source gives a feasible assignment x[v] = dist[v]. Negative cycle = infeasible. Applications: scheduling with precedence and deadline constraints, and many constraint satisfaction problems.
Problems you can solve with this pattern
3 problems · click any to start solving
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 satisfiedDifference constraints: given n variables and m constraints xⱼ - xᵢ ≤ wᵢⱼ, find an assignment satisfying all constraints or determine it's infeasible. Key: constraint xⱼ - xᵢ ≤ w is a triangle inequality on a graph edge i→j with weight w. Add virtual source s with edges s→i weight 0 for all i. Bellman-Ford from s: dist[j] - dist[i] ≤ w is automatically satisfied by shortest path distances.
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- Constraint xⱼ - xᵢ ≤ w → edge i→j with weight w
- Add virtual source s with 0-weight edges to all nodes
- Bellman-Ford gives feasible solution x[v] = dist[v]
- Negative cycle → infeasible
Equivalents:
- xⱼ - xᵢ ≥ k → xᵢ - xⱼ ≤ -k → reverse edge
- xⱼ = xᵢ → two constraints: xⱼ - xᵢ ≤ 0 and xᵢ - xⱼ ≤ 0
Applications: scheduling with precedence (task j must start ≥ d after task i), timing analysis in digital circuits, and any linear programming with only difference constraints.