Data Structures, Algorithms, & Applications in Java
Applications of Graphs
With Negative Edge Costs

Difference Equations

An important application of graphs with negative cost edges and of the Bellman-Ford algorithm is in the solution of a system of difference equations. Such a system comprises m equations of the form
xi-xj <= cq
where xi and xj are variables and cq is a constant.

A 4 variable system with 6 equations is given below.
x1 - x2 <= -2
x1 - x3 <= -6
x3 - x4 <= 5
x3 - x2 <= 4
x2 - x4 <= 1
x4 - x1 <= 1
One application of a system of difference equations is in event scheduling. Suppose we are to schedule four related events such that event 2 takes place at least two days after event 1; event 3 takes place at least 6 days after event 1; event 4 takes place no more than 5 days before event 3; event 2 takes place no more than 4 days before event 3; event 4 takes place no more than 1 day before event 2; and event 1 takes place no more than 1 day before event 4. If we let xi denote the time when event i takes place, then the xis must satisfy the 4 variable system with 6 equations given above. In fact, any assignement of nonnegative integers to the xis that satisfies all 6 equations defines a valid schedule for the 4 events.

We can transform any system of difference equations into a weighted digraph as follows.
  1. The weighted digraph has one vertex for each variable plus an additional vertex.
  2. There is a directed edge from this additional vertex to each of the remaining vertices. The weight of each of these edges is zero.
  3. For each equation xi - xj <= cq, there is a directed edge from the vertex that represents xj to the one that represents xi The weight of this edge is cq.
We shall show shortly that the constructed digraph has a negative-length cycle iff the system of difference equations it is constructed from has no solution. Further, the lengths of the shortest paths from the additional vertex to the remaining vertex define a feasible solution when the digraph has no cycle of negative length.

For our 4 variable 6 equation example, we let vertex i represent variable xi, 1 <= i <= 4 and we let vertex 5 be the additional vertex. The directed edges and their costs are {(5,1,0), (5,2,0), (5,3,0), (5,4,0), (2,1,-2), (3,1,-6), (4,3,5), (2,3,4), (4,2,1), (1,4,1)}, where the triple (u,v,c) denotes the directed edge from vertex u to vertex v whose cost is c.

Running the Bellman-Ford algorithm on the constructed digraph the lengths of the shortest paths from vertex 5 to vertices 1, 2, 3, and 4 are determined to be -6, -4, 0, and -5. The assignment x1 = -6, x2 = -4, x3 = 0, and x4 = -5 satisfies the 6 equations of our difference system. From this assignment, we may obtain other assignments by adding any constant to all xis. For example, by adding 6, we get the assignment x1 = 0, x2 = 2, x3 = 6, and x4 = 3. Since all times are now nonnegative, we can use this assignment as a schedule for the 4 events.

Theorem
  1. The constructed digraph has a negative-length cycle iff the system of difference equations it is constructed from has no solution.
  2. If the system has a solution, then the lengths of the shortest paths from the additional vertex to the remaining vertices defines a solution.

Proof
  1. Suppose that the constructed digraph has a negative-length cycle C. Without loss of generality, we may assume that this cycle is 1, 2, 3, ..., u, 1 where vertex i represents variable xi, 1 <= i <= u. Note that the additional vertex is on no cycle because it has no incoming edge. The edge (i,i+1) represents the equation xi+1 - xi <= cost(i,i+1), and the edge (u,1) represents the equation x1 - xu <= cost(u,1). Adding up both sides of the equations represented by the edges on the negative-length cycle C, we see that all variables cancel out on the left side to yield a left-side sum of zero. The sum of the right sides is the sum of the edge costs on the cycle. Since this sum is negative, adding the equations yields the equation
    0 <= sum of edge costs < 0
    which is a false statement. Therefore, no assignment to the xis can satisfy the given equations.

    The fact that if the system has no solution then the digraph has a negative-length cycle is established in a similar way.
  2. We may assume the digraph has no negative-length cycle. Consequently, there is a shortest path from the additional vertex to each of the remaining vertices. Let d(i) be the length of the shortest path from the additional vertex to the vertex i that represents variable xi. Let xi-xj <= cq be any equation in the given system. From the definition of d() it follows that d(i) <= d(j) + cost(j,i) = d(j) + cq. Therefore, d(i) - d(j) <= cq. Hence setting xi = d(i) for all i results in an assignment that satisfies all equations.