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. $
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 $$