16. Consider an undirected graph G with N vertices and M edges, where each edge (u, v)has a positive weight w(u, v). Let P=v0-v1-v2- Vk be a simple path from v0 to vk.Define the distance of P as w(P)= maxi=0 to k-1 { w(Vi, Vi+1)}. We say that a path P isoptimal from vertex s to vertex t, if w(P) is the smallest one among all paths form s to t.
【題組】(46)Which of the followings is correct?
(A) The optimal path has the so called optimal substructure.
(B) The optimal path between two vertices is unique.
(C) The problem can be solved with a greedy algorithm.
(D) The problem can be solved with dynamic programming.
(E) The Floyd-Warshall algorithm is the most efficient method for this problem.