edited by
14,679 views
37 votes
37 votes

Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ 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?

  1. $7$
  2. $8$
  3. $9$
  4. $10$
edited by

5 Answers

Best answer
29 votes
29 votes

2010-Q50-51


Answer is (B) $8$. The possible path is: $1 - 0, 0 - 4, 4 - 2$.

edited by
69 votes
69 votes

For getting quick answer just draw a tree of depth 3.  And compare various path. Although it is brute force, But this method will not take much time.

4 votes
4 votes

Given graph is

Path: 1 -> 0 -> 4 -> 2

So the minimum possible weight of a path from vertex 1 to vertex 2 in this graph

=4+1+3

=8

edited by
0 votes
0 votes
1 -> 0 -> 3 -> 4 -> 2
= 1 + 1 + 2 + 3
= 7
Also, this is the minimum cost spanning tree.
Answer:

Related questions

43 votes
43 votes
8 answers
1
26 votes
26 votes
4 answers
2