Consider the single-pair shortest path problem in a weighted directed graph G=(V, E) from a vertex s to t, where s denotes the source vertex and t represents the target/sink vertex. Let d_v denote the distance of any vertex v from the source vertex s. Moreover, let w(u,v) represent the weight of the edge (u,v). For each vertex z s, consider the set Distances_z, where

Distances_z = { d_(u,z) | where d_(u,z) = d_u + w(u,z) for each edge (u,z) in E }

To solve the single-pair shortest path problem using linear programming, we create the following linear program:

maximize d_t

subject to

d_v - d_u w(u,v) for each edge (u,v) in E

d_s= 0

Is it ok that we maximize d_t ? Why?

Select all that applies.

a. Yes, because minimizing it would result in an optimal solution where the distances of all vertices would be zero.

b. No. We should formulate it as a minimization linear program.

c. Yes, because an optimal solution requires the distance of the vertex z (i.e., d_z) to be the largest value that is less than or equal to the minimum of the values in Distances_z .

d. Yes, because both minimization and maximization would find the shortest path.