Linear programming formulation for the single-source shortest path problem - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:29:02Z https://cs.stackexchange.com/feeds/question/70894 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/70894 3 Linear programming formulation for the single-source shortest path problem hengxin https://cs.stackexchange.com/users/4911 2017-02-27T02:31:59Z 2017-02-27T03:58:59Z <p>In this <a href="http://www.cs.yale.edu/homes/aspnes/pinewiki/LinearProgramming.html" rel="nofollow noreferrer">course lecture; section 5.1</a>, single-source shortest path (SSSP) is formulated as the following linear program (LP):</p> <p>\begin{align} \max &amp;\sum d_u \\ \text{subject to} &amp; \\ d_v &amp;\le d_u + l_{uv} \quad \forall (u,v) \in E \\ d_s &amp;= 0 \end{align}</p> <p>The comment on the objective function is as follows (emphasis added):</p> <blockquote> <p>The variables $d_u$ represent the distances from $s$ to each vertex $u$. <strong><em>Maximizing the sum of the $d_u$ is done by maximizing each one individually, since increasing any single $d_u$ never forces us to decrease some other $d_v$</em></strong>. </p> </blockquote> <p>I can get its basic idea. However, how to argue that $(\max d_u \;\forall u \in V)$ is equivalent to $(\max \sum d_u)$ more rigorously? Specifically, why is that "increasing any single $d_u$ never forces us to decrease some other $d_v$"?</p> https://cs.stackexchange.com/questions/70894/-/70896#70896 2 Answer by Yuval Filmus for Linear programming formulation for the single-source shortest path problem Yuval Filmus https://cs.stackexchange.com/users/683 2017-02-27T03:58:59Z 2017-02-27T03:58:59Z <p>Any optimal solution to the problem must satisfy $$d_v = \min_{u\colon (u,v) \in E} (d_u + \ell_{uv}),$$ as well as $d_s = 0$, of course. Assuming the graph is connected, you can prove by induction on the length (number of edges) of a shortest path from $s$ to $v$ that $d_v$ is at most the distance from $s$ to $v$, which we denote by $d^*_v$. In particular, the optimal value is at most $\sum_v d^*_v$.</p> <p>On the other hand, it is not hard to check that $d_v = d^*_v$ (for all $v$) itself is a feasible solution, showing that the optimal value is exactly $\sum_v d^*_v$, and it is achieved only when $d_v = d^*_v$ for all $v$.</p>