# linear program, why is there an outgoing arc such that $d(s,v) = w(s,v)$

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

• So $w(s,v)$ is the weight of the edge $s \to v$ in $D$, but what is $d(s,v)$ in this context? – gt6989b Jun 26 '19 at 15:05
• I update the question – 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$$
• $u$ is a predecessor of $v$ – Kuifje Jun 26 '19 at 15:49