Question

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 ${\mathit{l}}_{\mathbf{e}}\mathbf{>}\mathbf{0}$.

a) Show that this is equivalent to finding an s - tflow fthat minimizes $\mathbf{\sum }_{\mathbf{e}}{\mathit{l}}_{\mathbf{e}}{\mathit{f}}_{\mathbf{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

role="math" localid="1659250472483" $$\begin{gathered} \mathit{m}\mathit{a}\mathit{x}\mathbf{}{\mathit{x}}_{\mathbf{s}}\mathbf{}\mathbf{-}\mathbf{}{\mathit{x}}_{\mathbf{t}} \\ {\mathit{x}}_{\mathbf{u}}\mathbf{-}{\mathit{x}}_{\mathbf{v}}\mathbf{\le }{\mathit{l}}_{\mathbf{u}\mathbf{v}}\mathbf{}\mathit{f}\mathit{o}\mathit{r}\mathbf{}\mathit{a}\mathit{l}\mathit{l}\mathbf{}\left(u,v\right)\mathbf{\in }\mathit{E} \end{gathered}$$

d) An interpretation for the dual is given in the box on page 223. Why isn’t our dual LP identical to the one on that page?

Short answer

a) It can be shown that the equivalent to an s - t flow f that minimizes $\sum _e{l}_e{f}_e$to size(f)=1.

b) Linear program:

$$\begin{gathered} \min \mathit{\sum }_{\mathit{e}}{l}_{\mathit{e}}{f}_{\mathit{e}} \\ \sum _{\left(s,u\right)\mathit{\in }E}{f}_{\left(s,u\right)}\mathit{=}\mathit{1} \\ \mathit{\sum }_{\mathit{(}\mathit{v}\mathit{,}\mathit{t}\mathit{)}\mathit{\in }\mathit{E}}{f}_{(v,t)}\mathit{=}\mathit{1} \\ \mathit{Ɐ}u\mathit{\in }\mathit{}V\mathit{,}u\mathit{\ne }s\mathit{,}u\mathit{\ne }t\mathit{:} \\ \mathit{\sum }_{\mathit{(}\mathit{w}\mathit{,}\mathit{u}\mathit{)}\mathit{\in }\mathit{E}}{f}_{(w,u)}\mathit{-}\mathit{\sum }_{\mathit{(}\mathit{u}\mathit{,}\mathit{v}\mathit{)}\mathit{\in }\mathit{E}}{f}_{(u,v)}\mathit{=}\mathit{0} \\ \mathit{Ɐ}u\mathit{\in }\mathit{}E\mathit{}\mathit{:}\mathit{}{f}_{\mathit{e}}\ge 0 \end{gathered}$$

c) Yes, the dual LP can be written as given.

d) Because, the dual in the box is written for undirected graph and the dual written in this problem is written for directed graph.

Step-by-step solution

Explain Directed Graph with edge

Consider the oriented graph's flowing network is represented by (V,E)A current node and a sinks vertex, where the source vertex is$s\in V$ and the sink vertex is $t\in V$, where edge$\left(u,v\right)\in E$ which has the capacity of$c\left(u,v\right)>0$ and flow $f\left(u,v\right)\ge 0$. As a result, the cost of sending flows down the edge (u,v).

Show that this is equivalent to finding an flow that minimizes subject to .

(a)

Consider that the length of the shortest path be s, then $s\le \sum _e{l}_e{f}_e$has to be proved. Knowing that f can be decomposed into one or more paths $p_1,p_2,p_3,\mathrm{K},p_n$. Since size(f) = 1, that means $\sum _e{l}_e{f}_e$is not less than the weighted average paths. Since the length of these paths is not less than s, $s\le \sum _e{l}_e{f}_e$. In addition, the shortest path is the flow path $s=\sum _e{l}_e{f}_e$, shows that the inequality can be changed as the equal sign.

Therefore, It has been shown that the equivalent to an s - t flow f that minimizes $\sum _e{l}_e{f}_{e}tosize\left(f\right)=1$.

Write the shortest path problem as a linear program.

(b)

A linear algorithm for the shortest-path problem is as follows,

Linear program:

$$\begin{gathered} \min \mathit{\sum }_e{l}_e{f}_e \\ \sum _{\mathit{(}s\mathit{,}u\mathit{)}\mathit{\in }E}{f}_{(s,u)}\mathit{=}\mathit{1} \\ \mathit{\sum }_{\mathit{(}v\mathit{,}t\mathit{)}\mathit{\in }E}{f}_{(v,t)}\mathit{=}\mathit{1} \\ \mathit{Ɐ}u\mathit{\in }\mathit{}V\mathit{,}u\mathit{\ne }s\mathit{,}u\mathit{\ne }t\mathit{:} \\ \mathit{\sum }_{\mathit{(}w\mathit{,}u\mathit{)}\mathit{\in }E}{f}_{(w,u)}\mathit{-}\mathit{\sum }_{\mathit{(}u\mathit{,}v\mathit{)}\mathit{\in }E}{f}_{(u,v)}\mathit{=}\mathit{0} \\ \mathit{Ɐ}e\mathit{\in }\mathit{}E\mathit{}\mathit{:}\mathit{}{f}_e\ge 0 \end{gathered}$$

Therefore, the linear program for the shortest path problem has been derived.

Step 4:Show that the dual LP can be written as given.

(c)

Consider the linear program in the part (b) solution, in that except for last $f_e\ge 0$, each vertex corresponds to a constraint.

For each vertex $v\in E$, multiply the constraint by the factor x, and add up all the constraints to get the equation $\mathit{\sum }_{\mathit{(}u\mathit{,}v\mathit{)}\mathit{\in }E}\left(x_u-x_v\right)f_{(u,v)}\mathit{=}{x}_{\mathit{s}}\mathit{-}{s}_{\mathit{t}}$.

The above equation is linked to the objective function, thus the dual LP can be written as given.

Therefore, yes It has been shown that the dual LP can be written as given.

Explain Why isn’t the given dual LP identical to the one on 223 page

(d)

Because, the dual in the box is written for undirected graph and the dual written in this problem is written for directed graph.