\input{template}
\input{macros}

\usepackage{graphicx}

\begin{document}

\lecture{26}{An example illustrating the LP duality based Shortest Path algorithm}{Pratyush Chandra}

\section{Formulations for an example graph}

Let us see the formulation for an example graph in Figure \ref{fig1}.

\begin{figure}[!h] 
\centering
\includegraphics{fig1.eps}
\caption{Given input graph}
\label{fig1}
\end{figure}


The integer LP is:

\begin{equation}
\text{min} x_{sb} + 3 * x_{sa} + 6 * x_{sd} + 2 * x_{ad} + 2 * x_{ac} + 6 * x_{bd} + 4 * x_{cs} + 5 * x_{ct} + 4 * x_{dt} + 2 * x_{tb}
\end{equation}
\begin{equation}
x_{sa} + x_{sb} + x_{sd} = 1
\end{equation}
\begin{equation}
x_{ct} + x_{dt} = 1
\end{equation}
\begin{equation}
\forall v \in V - \{s,t\} \sum_w x_{vw} - \sum_u x_{uv} = 0
\end{equation}
\begin{equation}
x_{uv} \geq 0
\end{equation}
\begin{equation}
x_{uv} \text{ is an integer}
\end{equation}

To obtain the linear program, we simple drop the constrant that $x_{uv}$ are integers.

And the corresponding dual is
\begin{equation}
\text{max } y_s - y_t
\end{equation}
\begin{eqnarray}
 \forall u,v \hspace{10mm} y_v - y_u \leq w_{uv} \\
 y_s - y_a \leq 3 \\
 y_s - y_b \leq 1 \\
 y_s - y_d \leq 6 \\
 y_a - y_c \leq 2 \\
 y_a - y_d \leq 2 \\
 y_b - y_c \leq 6 \\
 y_c - y_s \leq 4 \\
 y_c - y_t \leq 5 \\
 y_d - y_t \leq 4
\end{eqnarray}

Initially we set $y_{s} = y_{a} = y_{b} = y_{c} = y_{d} = y_{t} = 0 $. Now we keep incrementing $y_{i}$'s till some $y_v - y_u \leq w_{uv}$ becomes equality keeping $y_t = 0$.

\begin{table}[h!]
\centering
\begin{tabular}{|l|c|c|c|c|c|c|l|}
\hline
Iteration Number & $y_{s}$ & $y_{a}$ & $y_{b}$ & $y_{c}$ & $y_{d}$ & $y_{t}$ & Remark \\
\hline
1 & 1 & 1 & 1 & 1 & 1 & 0 & \\
\hline
2 & 2 & 2 & 2 & 2 & 2 & 0 & \\
\hline
3 & 3 & 3 & 3 & 3 & 3 & 0 & \\
\hline
4 & 4 & 4 & 4 & 4 & \underline{4} & 0 & $y_d - y_t = w_{dt} = 4$. Hence $y_d = 4$\\
\hline
5 & 5 & 5 & 5 & \underline{5} & \underline{4} & 0 & $y_c - y_t = w_{ct} = 5$. Hence $y_c = 5$\\
\hline
6 & 6 & \underline{6} & 6 & \underline{5} & \underline{4} & 0 & $y_a - y_d = w_{ad} = 2$. Hence $y_a = 6$\\
\hline
7 & 7 & \underline{6} & 7 & \underline{5} & \underline{4} & 0 & \\
\hline
8 & 8 & \underline{6} & 8 & \underline{5} & \underline{4} & 0 & \\
\hline
9 & \underline{9} & \underline{6} & 9 & \underline{5} & \underline{4} & 0 & $y_s - y_a = w_{sa} = 3$. Hence $y_s = 9$. Stop now.\\
\hline
\end{tabular}
\caption{Trace of the primal-dual algorithm on the example graph}
\label{table1}
\end{table}

See Figure \ref{fig2} for intermediate steps. Graph obtained after these iteration is \ref{fig2}(v). It contains some extra edges. So we apply reverse delete algorithm. First we delete maximum weight edge $e_{ct}$ and check for a path from {\it s} to {\it t}. Clearly such a path $s \implies a \implies d \implies t$ exist. Next we try to remove $e_{dt}$. This makes {\it t} unreachable from {\it s}. Hence we stop here. Graph thus obtained is shown in Figure \ref{fig2}(vi). Shortest path thus obtained is $s \implies a \implies d \implies t$.

We also see that value of shortest path thus obtained is $y_s - y_t = 9$.

\begin{figure} 
\centering
\includegraphics[scale=0.7]{fig2.eps}
\caption{Intermediate Steps}
\label{fig2}
\end{figure}


\end{document}