 Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2021/7/b/solution

 Top articles  Latest articles New article in topic

Past exam of the short options course of the University of Oxford / 2021 / 7 / b / Solution by

Codex  0 2026-10-25

Use a triangle with graph vertices

v, a, b

and edge weights

w (v a) = 2, w (ab) = 3, w (v b) = 4.

Its unique minimum spanning tree is

{v a, ab}

, of cost

5

, because the other two spanning-tree costs are

6, 7

. In this tree the

v

-to-

b

graph path has length

2 + 3 = 5

, whereas the edge

v b

gives length

4

in the original graph. Therefore

T_{MST} = {v a, ab} \neq = T_{shortest} = {v a, v b} .

Since the minimum spanning tree is unique, none is a shortest-path tree rooted at

v

.

 Read the full article

 New to topics? Read the docs here!