GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
840 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 (87.2k points)  
edited by | 840 views

3 Answers

+9 votes
Best answer

2010-Q50-51

 


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

answered by Junior (823 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 ?

@gshivam

Using bellman ford is fine, but it is very time consuming.

As first we have to convert the undirected graph to a directed one https://cs.stackexchange.com/questions/24768/shortest-path-in-weightedpositive-or-negative-undirected-graph

And then apply Bellman ford from vertex 1 as src.

I tried as below ::(may be helpful to other readers)

But, can anyone suggest any other shortcut method??

 

ravi_ssj4 no.

+3 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.

 

 

answered by Active (2k points)  
Nice approach :)
How this tree is drawn?? Can u please explain in detail
0 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

answered by Veteran (37.5k points)  
edited by
it was wrong now corrected


Top Users Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,979 questions
33,554 answers
79,348 comments
31,011 users