GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
473 views

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
asked in Algorithms by Veteran (76k points)  
edited by | 473 views

2 Answers

+7 votes
Best answer

2010-Q50-51

 


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

answered by Junior (813 points)  
selected by

 

Is there any shortcut method for determining the mini possible wt of a path from vertex 1 to 2.

Because if we take the brute force approach it is very time consuming .Moreover, there are chances of error as well.

@vidhi ....we can apply bellman ford algorithms upto 3 iterations 

Start from vertex 1 as source

i=1 representing atmost 1 edge

i=2 representing atmost 2 edge

i=3 representing atmost 3 edge

Use Bellman Ford only for vertex 2, to save time.....

We have to apply bellmanford upto 4(5 - 1) iterations right ?
+1 vote

Given graph is

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

=4+1+2+3

=10

answered by Veteran (36.3k points)  


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,445 questions
26,757 answers
60,936 comments
22,954 users