試題詳解

複選題
(47) Suppose there are 5 vertices, v₁, v₂,... , v₅ and the weight between v_i and v_j is ((i-j)*(i-j) mod 5)+1, where i≠j. Which of the followings is correct?
(A) There is no solution for this input.
(B) The weight of the optimal solution between any pair of vertices is 2.
(C) There is a pair of vertices which has the optimal solution as 5.
(D) The optimal path between any pair of vertices is unique.
(E) The optimal path and the shortest path between v2 and v4 are the same path.