The GATE Grind

GATE 2011 CS (CS1) – Question 65

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0<|i−j|≤2; edge weight is i+j. The drawing shows n=4. For n=10, find the weighted path length from v₅ to v₆ in the MST.

Diagram for GATE 2011 CS (CS1) question 65
  1. 11
  2. 25
  3. 31
  4. 41

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 31

Explanation

The MST contains (1,2) and edges (j−2,j), j≥3. The path is v₅→v₃→v₁→v₂→v₄→v₆. Its edge weights are 8,4,3,6,10, summing to 31, C. This is weighted length, not the number of edges.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →