Consider a directed graph $G=(V, E)$, where each edge $e \in E$ has a positive edge weight $c_e$. Determine the appropriate choices for the blanks below so that the value of the following linear program is the length of the shortest directed path in $G$ from $s$ to $t$. (Assume that the graph has at least one path from $s$ to $t$.)
$\begin{align}
\quad \underline{(\text{blank } 1)\text{imize}} \qquad X_{t} & \\
\quad \qquad {\text{s.t.}} \qquad X_{s}&\quad = \quad 0 \\
\quad \qquad X_{w}-X_{v}&\quad \underline{(\text{blank } 2)} & c_{e} \quad \text{(for each edge }e = (v, w) \in E).
\end{align}$
- $\text{blank }1: \max, \text{blank }2:\; \leq $
- $\text{blank }1: \max, \text{blank }2:\; \geq$
- $\text{blank }1: \min, \text{blank }2:\; \leq$
- $\text{blank }1: \min, \text{blank }2:\; \geq$
- $\text{blank }1: \min, \text{blank }2:\; =$
