in Algorithms recategorized ago by
56 views
1 vote
1 vote

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:\; =$
in Algorithms recategorized ago by
by
56 views

Please log in or register to answer this question.

Answer:

Related questions