Algorithms: Difference Constraints I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem:


  Consider the following set of difference constraints:

x1 - x4 &lt;= 1  
x2 - x1 &lt;= 2  
x2 - x4 &lt;= 0  
x3 - x1 &lt;= 1  
x4 - x1 &lt;= -1  
x4 - x3 &lt;= -2  

  
  What is the solution that will be provided by the shortest path based algorithm for this set of constraints?  


I know that you are supposed to create a graph using these constraints, so that there is one edge per constraint and one node per variable. So, for this problem, there would be four nodes: x1, x2, x3, and x4. There would also be six edges because there are six constraints. The first constraint should make an edge from x4 to x1 with a weight of 1. The second constraint should make an edge from x1 to x2 with a weight of 2. The rest of the constraints are made into edges following the same pattern.

So after you create the graph, you're supposed to run a shortest path algorithm on it, and it somehow gives you the values for each variable. This is the part that I am unsure about.

The answer that I got when I did this was that x1 = 0, x2 = -1, x3 = 0, and x4 = -2. Unfortunately, this doesn't work because of the first and third constraints.

Can someone walk me through how to get the right answer using the shortest path based algorithm for this question? Thanks!
You seem to already know the correct procedure but you have calculated the shortest paths incorrectly.

Procedure: 


Create a source vertex ($s$) and add zero-weight edges from the source to all vertices.
Compute single-source shortest path from the source to each vertex. (If a negative-weight cycle exists, there is no solution to the set of constraints.)
The constraints are solved by assignments $x_i = \delta(s, x_i)$ where $\delta(s, x_i)$ is the shortest path from $s$ to $x_i$.



x1 = -1 (s -> x3 -> x4 -> x1)
x2 = -2 (s -> x3 -> x4 -> x2)
x3 =  0 (s -> x3)
x4 = -2 (s -> x3 -> x4)


Source: See slides 6-10 of http://courses.csail.mit.edu/6.006/spring11/lectures/lec17.pdf