 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/functional-programming-design-and-analysis-of-algorithms-resit/8/b/iii/solution

False. Take a triangle with

w (ab) = w (b c) = 2

and

w (a c) = 3

ab

and

b c

, with total weight 4. The shortest path from

a

c

in the original graph is the direct edge of weight 3; the tree's only path has weight 4. A minimum spanning tree optimizes total tree weight, not every pairwise path length.

 New to topics? Read the docs here!