patternMinor
Linear programming formulation for the single-source shortest path problem
Viewed 0 times
problemlinearthepathshortestsourceprogrammingsingleforformulation
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$"?
\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$"?
Solution
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$.
$$
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$.
Context
StackExchange Computer Science Q#70894, answer score: 2
Revisions (0)
No revisions yet.