AlgoVerse

Difference constraints

Turn a system of inequalities x_j − x_i ≤ b into a graph and solve it with Bellman–Ford: the shortest-path distances are a solution, and a negative cycle means there is none.

We have a system of inequalities of the form x_j − x_i ≤ b (in scheduling, say: "job j starts at most b units after job i"). We want values for x that satisfy them all, or to learn that none exist.

Read the full explanation ↓
Input:
C 8×3PDF export

Eight constraints on five variables (the CLRS example); one solution: x = (−5, −3, 0, −1, −4).

  1. def difference_constraints(C):
  2. # Each row [j, i, b] means x_j - x_i <= b: an edge i -> j of weight b. Vertex 0 is a source with 0-edges to all.
  3. n = 0
  4. for j, i, b in C:
  5. n = max(n, i, j)
  6. edges = []
  7. for v in range(1, n + 1):
  8. edges.append([0, v, 0])
  9. for j, i, b in C:
  10. edges.append([i, j, b])
  11. x = [0] + [float("inf")] * n
  12. for rnd in range(1, n + 1):
  13. changed = False
  14. for u, v, w in edges:
  15. if x[u] + w < x[v]:
  16. x[v] = x[u] + w
  17. changed = True
  18. if not changed:
  19. break
  20. for u, v, w in edges:
  21. if x[u] + w < x[v]:
  22. return None
  23. solution = x[1:]
  24. return solution

Invariant: After round k, x[v] is at most the length of the shortest path from 0 to v with at most k edges.

Start

x—
solution—

Local variables

Orange = changed in this step

C list

[1, 2, 0][1, 5, -1][2, 5, 1][3, 1, 5][4, 1, 4][4, 3, -1][5, 3, -3][5, 4, -3]

Call stack

  1. difference_constraints()line 1
Step 1 of 191
Black = settled · Orange = key stepgraph: 0/1 · relax: 0/11 · settled: 0/1 · solution: 0/1
    Explanation

    The problem

    We have a system of inequalities of the form x_j − x_i ≤ b (in scheduling, say: "job j starts at most b units after job i"). We want values for x that satisfy them all, or to learn that none exist.

    Turning it into shortest paths

    Each constraint x_j − x_i ≤ b is an edge i → j of weight b; it is exactly the shortest-path condition d(j) ≤ d(i) + w(i, j). Add a source vertex 0 with a weight-0 edge to every variable. Now:

    • if the graph has no negative cycle, x_i = δ(0, i) is a solution;
    • if it has one, adding up the constraints around the cycle gives 0 ≤ a negative number: there is no solution.

    Bellman–Ford tells the two apart: O(n·m).

    A note

    If x is a solution, so is x + c; this algorithm gives the solution with every x_i ≤ 0 and the largest sum.

    The input

    Each row [j, i, b] means x_j − x_i ≤ b; the variables are numbered from 1.