91 views

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}

1. $\text{blank }1: \max, \text{blank }2:\; \leq$
2. $\text{blank }1: \max, \text{blank }2:\; \geq$
3. $\text{blank }1: \min, \text{blank }2:\; \leq$
4. $\text{blank }1: \min, \text{blank }2:\; \geq$
5. $\text{blank }1: \min, \text{blank }2:\; =$

1 vote