# Difference Constraints And Shortest Paths

and

*E* = {(*v _{i}*,

*v*) :

_{j}*x*-

_{j}*x*≤

_{i}*b*is a constraint} ∪{(

_{k}*v*

_{0},

*v*

_{1}), (

*v*

_{0},

*v*

_{2}), (

*v*

_{0},

*v*

_{3}),..., (

*v*

_{0},

*v*)} .

_{n}
The additional vertex *v*_{0} 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*, plus an additional vertex

_{i}*v*

_{0}. The edge set

*E*contains an edge for each difference constraint, plus an edge (

*v*

_{0},

*v*) for each unknown

_{i}*x*. If

_{i}*x*-

_{j}*x*≤

_{i}*b*is a difference constraint, then the weight of edge (

_{k}*v*,

_{i}*v*) is

_{j}*w*(

*v*,

_{i}*v*) =

_{j}*b*. The weight of each edge leaving

_{k}*v*

_{0}is 0. Figure 24.8 shows the constraint graph for the system (24.3)-(24.10) of difference constraints.

*v*

_{0},

*v*

_{i}) is shown in each vertex

*v*. A feasible solution to the system is

_{i}*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.