0

When looking around for formulating the shortest path problem as a LP I found this:

https://www.cs.princeton.edu/~rs/AlgsDS07/22LinearProgramming.pdf

At slide 39 they give an example

example

But in my eyes, this solution doesn't satisfy the inequalities. For example,

x_7 + 44 <= x_t 
with x_7 = 15 and x_t = 50 leads to 
59 <= 50

What is my misunderstanding?

IsolatedSushi
  • 13
  • 1
    Those inequalities look backwards. If $x_t$ is the shortest distance to node $t$ then any other path to node $t$ should be greater than or equal to that. Therefore, we should get that $x_7+44\ge x_t$. – John Douma Oct 28 '20 at 15:11

1 Answers1

1

The constraint inequalities all seem to be backwards to me. Take the first one, $x_s+9\leq x_2$. We know a way to get from $s$ to $2$ in $9$ so the shortest path to $2$ is at most the shortest distance to $s$ plus $9$.

The constraint should read $x_2\leq x_s +9$.

saulspatz
  • 53,131