Difference Constraints And Shortest Paths


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.

Figure 24.8: The constraint graph corresponding to the system (24.3)-(24.10) of difference constraints. The value of δ(v0, vi) is shown in each vertex vi. A feasible solution to the system is x = (-5, -3, 0, -1, -4).

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.