# Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP):

\begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le d_u + l_{uv} \quad \forall (u,v) \in E \\ d_s &= 0 \end{align}

The comment on the objective function is as follows (emphasis added):

The variables $d_u$ represent the distances from $s$ to each vertex $u$. 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$.

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$"?

• I suggest ignoring this unhelpful statement, and instead trying to prove independently that this program has a unique optimal solution, in which $d_u$ is indeed the shortest distance from $s$ to $u$ (if it's true!). – Yuval Filmus Feb 27 '17 at 3:52

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