and
E = {(vi, vj) : xj - xi ≤ bk is a constraint} ∪{(v0, v1), (v0, v2), (v0, v3),..., (v0, vn)} .
The additional vertex v0 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 vi for each unknown xi , plus an additional vertex v0. The edge set E contains an edge for each difference constraint, plus an edge (v0, vi) for each unknown xi . If xj - xi ≤ bk is a difference constraint, then the weight of edge (vi , vj) is w(vi, vj) = bk. The weight of each edge leaving v0 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.