and

E = {(v_i, v_j) : x_j - x_i ≤ b_k is a constraint} ∪{(v₀, v₁), (v₀, v₂), (v₀, v₃),..., (v₀, v_n)} .

The additional vertex v₀ is incorporated, as we shall see shortly, to guarantee that every other vertex is reachable from it. Thus, the vertex set V consists of a vertex v_i for each unknown x_i , plus an additional vertex v₀. The edge set E contains an edge for each difference constraint, plus an edge (v₀, v_i) for each unknown x_i . If x_j - x_i ≤ b_k is a difference constraint, then the weight of edge (v_i , v_j) is w(v_i, v_j) = b_k. The weight of each edge leaving v₀ is 0. Figure 24.8 shows the constraint graph for the system (24.3)-(24.10) of difference constraints.

The following theorem shows that we can find a solution to a system of difference constraints by finding shortest-path weights in the corresponding constraint graph.