If any other information is needed, please feel free to ask me. I'm beginning my learning in graph theory and in optimization.

Let's call $D = (V,A)$ a directed graph. $w : A \to \mathbb R$, arc weights, $s \in V$. We also assume that there is a path from $s$ to any other vertex of $V$. The linear program is the following :

$$ \max \sum_{v \in V \backslash { s } } x_v $$ s.t. $$ x_v - x_u \leq w(u,v) , \forall (u,v) \in A$$ $$ x_s \leq 0.$$

apparently, if there is no negative cycle in $D$, there has to be an outgoing arc $(s,v) \in A $ such that $d(s,v) = w(s,v)$. Do you know why ?

$d(u, v) $ denotes the length of the shortest path from $u$ to $v. $

  • $\begingroup$ So $w(s,v)$ is the weight of the edge $s \to v$ in $D$, but what is $d(s,v)$ in this context? $\endgroup$ – gt6989b Jun 26 '19 at 15:05
  • $\begingroup$ I update the question $\endgroup$ – Marine Galantin Jun 26 '19 at 15:13

This follows from the fact that by definition $$ d(s,v) = \min_{u|(u,v) \in A}\{d(s,u) + \omega(u,v) \} $$ Indeed, this is equivalent to $$ d(s,v) \le d(s,u) + \omega(u,v) \quad \forall (u,v) \in A $$ or $$ d(s,v) - d(s,u) \le \omega(u,v) \quad \forall (u,v) \in A $$

  • $\begingroup$ What represents u in my question? I m sorry i m really lost. And you can do that bc there is no negative cycle, then distance is well defined? $\endgroup$ – Marine Galantin Jun 26 '19 at 15:48
  • $\begingroup$ $u$ is a predecessor of $v$ $\endgroup$ – Kuifje Jun 26 '19 at 15:49
  • $\begingroup$ Yes this is only true is there are no cycles. $\endgroup$ – Kuifje Jun 26 '19 at 15:50
  • $\begingroup$ Oh so since u = s in my case, d(u, s) =0. But you give an inequality and i need an equality. $\endgroup$ – Marine Galantin Jun 26 '19 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.