GATE CSE
First time here? Checkout the FAQ!
x

GATE 2016-1-38

+6 votes
2.6k 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.6k 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 // 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 (425 points)  
selected 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
+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.7k 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.1k 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 Feb 2017
  1. Arjun

    5278 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3942 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1660 Points

Monthly Topper: Rs. 500 gift card

20,856 questions
26,009 answers
59,671 comments
22,107 users