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

  • $\begingroup$ 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!). $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.