# GATE2010-51

5.2k 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$

edited
1
Think this using tree approach ... Take 1 as root ... consider only those paths which has destination vertex as 2 and 3 edges between them ... This way u will get 1-0-4-2 = 8 ... So option B ...

Hence proved ... :p
0
but 3rd vertex has the minimal weight compared to 4th vertex...could you please explain which algorithm you used and how you got the answer...

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

edited by
11

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.

10

@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.....

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

@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.

But, can anyone suggest any other shortcut method??

0

ravi_ssj4 no.

4

I tried the below approach and it worked!!

We want to reach vertex 2 from 1.

What now I do is, scan the adjacency matrix in a column-wise fashion and now I determine the shortest edge by which I can reach a vertex i in the graph.

Like, to reach vertex 2, I can reach with a minimum cost from vertex 4 with cost 3.

Following the similar pattern, I build a path tree, which goes from vertex 1 to vertex 2.

Now, this path from vertex 1 to 2 consist of 4 edges but I want a path with at most 3 edges.

So, now using vertex 1 as source and other vertices 0,3,2 I multiplex them one by one and check which one will give me the shortest path.

And cost comes out to be 8.

0
1-0-3-4-2 .. By this we can get 7 as answer
0
but from 0 the minimum cost is 1 towards node 3... y u chose 4?
1
I think we can reach from vertex 1 to vertex 2 in 7 by going like this :

1-0 , 0-3 , 3-4 , 4-2 = 1+1+2+3
0
But you have taken 4 edges into path.

In the question limit is .. Atmost 3. (0, 1, 2 or 3 edges ).

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.

8
Nice approach :)
0
How this tree is drawn?? Can u please explain in detail
2
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?
1

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.

6
This is the best answer for me,Quick and no chances of error.
0
Method to draw this tree: Consider vertex 1 as node and draw edges to other nodes except vertex 1 for the first level with their respective edges. Similarly for 2nd level include vertex 2 when you reach the 2nd last level.

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
it was wrong now corrected
1 -> 0 -> 3 -> 4 -> 2
= 1 + 1 + 2 + 3
= 7
Also, this is the minimum cost spanning tree.
0
@jai

it should be 7 right ?

what was the gate answer key ?
0
At most 3 edges should be used. Please read the question carefully.
1

Brother correct your answer ! It is clearly mentioned in the question that only 3 edges should be taken and you took 4 edges in your approach.

Correct answer is 8 by 1 ---> 0 ---> 4 ---> 2.

## Related questions

1
7.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\}$ ... $T$ in this graph such that vertex 0 is a leaf node in the tree $T$? $7$ $8$ $9$ $10$
What is the value printed by the following C program? #include<stdio.h> int f(int *a, int n) { if (n <= 0) return 0; else if (*a % 2 == 0) return *a+f(a+1, n-1); else return *a - f(a+1, n-1); } int main() { int a[] = (12, 7, 13, 4, 11, 6); printf("%d", f(a, 6)); return 0; } $-9$ $5$ $15$ $19$
The weight of a sequence $a_0,a_1, \dots, a_{n-1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}$. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the maximum possible weight of ... $X$ is equal to $max(Y, a_0+Y)$ $max(Y, a_0+Y/2)$ $max(Y, a_0 +2Y)$ $a_0+Y/2$
Two alternative packages $A$ and $B$ are available for processing a database having $10^k$ records. Package $A$ requires $0.0001 n^2$ time units and package $B$ requires $10n\log_{10} n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$? $12$ $10$ $6$ $5$