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 <= 1 x2 - x1 <= 2 x2 - x4 <= 0 x3 - x1 <= 1 x4 - x1 <= -1 x4 - x3 <= -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!