Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry…
2010
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
W = \(\begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & 4 & 9 \\ 8 & 12 & 0 & 7 & 3 \\ 1 & 4 & 7 & 0 & 2 \\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)
What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
- A.
7
- B.
8
- C.
9
- D.
10
Attempted by 75 students.
Show answer & explanation
Correct answer: B
Correct. Path 1->0->4->2 has weights 1+4+3 = 8 and uses 3 edges. Direct 1->2 is 12 and the best 2-edge path is 1->0->2 = 9, so 8 is the minimum with ≤3 edges.
A video solution is available for this question — log in and enroll to watch it.