The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1.1k 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 (98k points)
edited by | 1.1k views

3 Answers

+13 votes
Best answer

2010-Q50-51

 


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

answered by Junior (843 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.

+6 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 Boss (6.6k points)
Nice approach :)
How this tree is drawn?? Can u please explain in detail
Why have you not expanded the last 1->4->0>2 and 1->4->3->2 ,although it is not shortest but why did you not find in the tree diagram?

Why have you not expanded the last 1->4->0>2 and 1->4->3->2 ,although it is not shortest but why did you not find in the tree diagram?

rahul sharma 5 ji. Good point but while making tree i realized that they will not give minimum. But yes we can draw them also to make the diagram more elegant and clear. 

+1 vote

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 (39.3k points)
edited by
it was wrong now corrected


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,844 answers
91,376 comments
34,721 users