Solution Found!
A linear program for shortest path. Suppose we want to compute the shortest path from
Chapter 7, Problem 7.28(choose chapter or problem)
A linear program for shortest path. Suppose we want to compute the shortest path from node \(s\) to node \(t\) in a directed graph with edge lengths \(l_{e}>0\).
(a) Show that this is equivalent to finding an \(s-t\) flow \(f\) that minimizes \(\sum_{e} l_{e} f_{e}\) subject to size \((f)=1\). There are no capacity constraints.
(b) Write the shortest path problem as a linear program.
(c) Show that the dual LP can be written as
\(\begin{array}{l}\max x_{s}-x_{t}\\x_{u}-x_{v} \leq l_{u v} \text{ for all } (u, v) \in E\end{array}\)
(d) An interpretation for the dual is given in the box on page 209. Why isn't our dual LP identical to the one on that page?
Questions & Answers
QUESTION:
A linear program for shortest path. Suppose we want to compute the shortest path from node \(s\) to node \(t\) in a directed graph with edge lengths \(l_{e}>0\).
(a) Show that this is equivalent to finding an \(s-t\) flow \(f\) that minimizes \(\sum_{e} l_{e} f_{e}\) subject to size \((f)=1\). There are no capacity constraints.
(b) Write the shortest path problem as a linear program.
(c) Show that the dual LP can be written as
\(\begin{array}{l}\max x_{s}-x_{t}\\x_{u}-x_{v} \leq l_{u v} \text{ for all } (u, v) \in E\end{array}\)
(d) An interpretation for the dual is given in the box on page 209. Why isn't our dual LP identical to the one on that page?
ANSWER:Step 1 of 5
The shortest path is defined for any type of graph, such as an undirected graph, directed graph, or mixed graph. The shortest path from vertex s to t is a directed path such that there is no other path that has a lower weight. Given: A directed graph and the length of the edge is \(l_e\).