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 &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}

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