GATE CSE
First time here? Checkout the FAQ!
x

GATE 2016-1-38

+6 votes
2.9k views
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$.

   

  W=$\begin{bmatrix} 0&2 &8 &5 \\ 2&0 &5 &8 \\ 8&5 &0 &x \\ 5& 8 &x &0 \end{bmatrix}$

The largest possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________
asked in Algorithms by Boss (8.9k points)   | 2.9k views
12 is correct answer.
Thanx. I used floyd warshal to solve it. Can u post ur solution?

4 Answers

+20 votes
Best answer

Let us list down the shortest edge between each pair of vertices x,y in the graph

x y shortest path from x to y
1 2 2
1 3 there is a direct path from 1 to 3 of weight 8.We can also chose to go via node 4 with total path weight 5+x. If 5+ x < 8 (x < 3) then shortest path is 5+x otherwise shortest path is the weight of the direct path i.e 8
1 4 5
2 3 5
2 4 there is a direct path from 2 to 4 of weight 8.We can also chose to go via node 3 with total path weight 5+x. If 5+ x < 8 (x < 3) then shortest path is 5+x otherwise shortest path is the weight of the direct path i.e 8
3 4 We can chose to go through the direct path of weight x or via node to with weight 5+8 = 13. If x < 13 then we will choose x to be the shortest path otherwise 13 is the shortest path

 

  • Case 1: Let us say x < 3. Say x = 2.

When we put x = 2 the above table is modified as

x y shortest path from x to y
1 2 2
1 3 7
1 4 5
2 3 5
2 4 7
3 4 2  // Note that the shortest path between node 3 and 4 is x = 2

 

  • Case 2: 3 <= x < 13. Let's say x = 12. The table is now modified as
x y shortest path from x to y
1 2 2
1 3 8
1 4 5
2 3 5
2 4
3 4 12   // Note that the shortest path between node 3 and 4 is x =12

Now the question asks you to find the largest possible integer value of x such that shortest path between atleast one pair of nodes in the graph is equal to x. for values x = 2,3,4,....,12 the shortest path between node 3 and 4 is equal to x.

The largest among this is x = 12. So the answer is 12

answered by Junior (503 points)  
edited by
best explanation
y can't 13 be the answer ?

In the above graph of jankyMurthy..label nodes 1=A 2=B 3=C and 4=D.

Now u can take path from C to D as direct edge with weight 13 or indirect from C to A(5) and A to D(8).. which is again 13...so why not 13 can be the maximum weight ?

 

A correction: 

The shortest distance between node 3 and node 4 is 12 (via node4, node1, node2, node3) or x (via direct path). So if you keep x=12, at least one shortest path between some pair of vertices will contain the edge with weight x.
 

If you consider the shortest path as 13 (5+8 or 8+5), then answer would be 13, which is not the case.

@nitesh Bcz from 3 -> 2 ->1-> 4 is a path with weight 12
Ya i got it,my bad..

thanks for pointing that path
Does this question use the concept of Floyd Warshal's algo?
+24 votes
Answer is x=12.  Here, when we read the last sentence of the question, i.e the largest possible integer value of x. when x=11 , shortest path is edge with weight x only. But when x=12, there are 2 shortest paths, and we can say that the edge with weight x is also a shortest path. Atleast 1 shortest path contain edge x. So answer will be 12.
answered by Active (1.8k points)  
By mistake of not reading question correctly. they have mentioned atleast 1 shortest path must contain edge x. 12 and 13 are already there, so thought of 11 coming as shortest path. but 12 is enough. 12 is the answer
I can't understand.plz draw the graph.
why not 4.after 8 then two path 5 and x.so x=4

In question this line( at least one shortest path between some pair of vertices will contain the edge with weight xx) should not have written edges/edge instead of edge only ? Because shortest path may contain more than one edge and the weight of all edges have to be x .

 

 
+9 votes

ans is simple....if we want to get shortest path between c and d without x its 8+5=13 so to get the shortest path between c and d we can include weight 12 which is maximum...correct me if i am wrong...

 

answered by Loyal (3.2k points)  
shortest path between c to d from your dig is c-b-a-d = 12.
The ques is not that straight, and it says that for what largest value of x, atleast one shortest path will contain x.
If we take x = 12, there will be two shortest path between c and d, ie. c-b-a-d and c-d iteself.
so taking x= 12, "at least one shortest path between any pair of vertices" may belong to it.
+3 votes
x = 12
answered by Junior (519 points)  
Explanation?
There already exist a path of  weight 12 from 4th node to 5th node. So i think it should be 11.
please see the explanation of answer given by me
x=4
in the Qtn they have given a hint "at least one shortest path"

so there could be more number of shortest paths of equal weight. 11 will not be correct, becoz , then this path of weight 11 will be the ONLY shortest path. Hence we have to find a path of same least weight. so x will be only 12, and not any other value.
Answer:

Related questions



Top Users May 2017
  1. akash.dinkar12

    3292 Points

  2. pawan kumarln

    1652 Points

  3. sh!va

    1650 Points

  4. Arjun

    1424 Points

  5. Bikram

    1372 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1142 Points

  8. Angkit

    1044 Points

  9. LeenSharma

    904 Points

  10. srestha

    718 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    458 Points

  2. Arnab Bhadra

    402 Points

  3. pawan kumarln

    278 Points

  4. Ahwan

    236 Points

  5. bharti

    194 Points


22,786 questions
29,121 answers
65,184 comments
27,661 users