Linear programming formulation for the single-source shortest path problem

Question

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

Answer 1

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

Answer 2

The claim that "increasing any single $d_u$ never forces us to decrease some other $d_v$" can be seen from the constraint $d_v \leq d_u + l_{uv}$. Here, increasing $d_u$ will not cause a violation in this particular constraint, while increasing $d_v$ would require $d_u$ to increase (not decrease) in order to keep the constraint true.

Now for the "maximizing each one individually" part, recall that the single source single destination shortest paths problem is solved by having the above linear program maximizing a single $d_u$ instead of the sum. From the claim in the paragraph above, we see that maximizing the sum results in a solution for which it is impossible to improve any individual $d_u$ (if it were, then since we need not decrease anything, it would be guaranteed to contradict our initial assumption of having already maximized the sum).

Hence maximizing the sum gives a solution for which each individual $d_u$ has the same value as if it were individually maximized in the single-pair case, and thus maximizing the sum optimally solves the single-source all destination problem.