91Ó°ÊÓ

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∈V$ and the sink vertex is $t∈V$, where edge$\left(u,v\right)∈E$ which has the capacity of$c\left(u,v\right)>0$ and flow $f\left(u,v\right)â‰\yen 0$. As a result, the cost of sending flows down the edge (u,v).

(a)

Consider that the length of the shortest path be s, then $s≤\underset{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 $\underset{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≤\underset{e}{∑}{l}_e{f}_e$. In addition, the shortest path is the flow path $s=\underset{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 $\underset{e}{∑}{l}_e{f}_{e}tosize\left(f\right)=1$.

(b)

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

Linear program:

$$\begin{gathered} \min \underset{e}{\mathit{∑}}{l}_e{f}_e \\ \underset{\mathit{(}s\mathit{,}u\mathit{)}\mathit{∈}E}{∑}{f}_{(s,u)}\mathit{=}\mathit{1} \\ \underset{\mathit{(}v\mathit{,}t\mathit{)}\mathit{∈}E}{\mathit{∑}}{f}_{(v,t)}\mathit{=}\mathit{1} \\ \mathit{â\pm ¯}u\mathit{∈}\mathit{}V\mathit{,}u\mathit{≠}s\mathit{,}u\mathit{≠}t\mathit{:} \\ \underset{\mathit{(}w\mathit{,}u\mathit{)}\mathit{∈}E}{\mathit{∑}}{f}_{(w,u)}\mathit{-}\underset{\mathit{(}u\mathit{,}v\mathit{)}\mathit{∈}E}{\mathit{∑}}{f}_{(u,v)}\mathit{=}\mathit{0} \\ \mathit{â\pm ¯}e\mathit{∈}\mathit{}E\mathit{}\mathit{:}\mathit{}{f}_eâ‰\yen 0 \end{gathered}$$

(c)

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

For each vertex $v∈E$, multiply the constraint by the factor x, and add up all the constraints to get the equation $\underset{\mathit{(}u\mathit{,}v\mathit{)}\mathit{∈}E}{\mathit{∑}}\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.

(d)

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