GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
509 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 (76.3k points)  
edited by | 509 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 Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users