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 dv 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 LaTeX: \ne ≠ s, consider the set Distancesz, where

Distancesz = { d(u, z) | where d(u, z) = du + 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 dt

subject to

dv - du <= w(u, v) for each edge (u, v) in E

ds= 0

Is it ok that we maximize dt ? 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., dz) to be the largest value that is less than or equal to the minimum of the values in Distancesz .
d. Yes, because both minimization and maximization would find the shortest path.