GATE CSE 2016 Set 1 | Question: 38

Question

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

Comments

If you see the line “at least one shortest path between some pair of vertices” in question it means that there can be more than 1 shortest path between pair of vertices and out of that n shortest path at least one of them uses edge x. In that way 12 goes as the answer. If word guaranteed  is used in question then we might had to go with 11.

---

No Dipak you are not reading it in context I think, see they have said basically you choose the largest value of ‘x’, and then get shortest path between each vertex, (not in all possible ways you can get shortest path between each vertex) for that chosen value of ‘x’ , so that x will edge in some vertex shortest path, which in turn means means give me value of ‘x’ for which it is guaranteed to be used in shortest path between some pair of vertex of the graph

---

Revision of the single shortest Path NPTEL
https://youtu.be/VQqVDNCJ1jA

Answer 1

x =12.

if you take x =13, then there is path between C and D -> C-B-A-D which is 12, so x=13 will not consider as shortest path.

now if you take 11, then it will be shortest path but not largest, when x=12 then then there is two path between D and C which is 12. Both are the shortest path. So, it is shortest path which is largest.

Answer 2

Draw the graph by considering the values given in the matrix as:

                                                                           

We have to find the largest possible integer value of x for which at least one shortest path between some pair of vertices will contain the edge (3,2) that is x.

After we draw the graph we can find it in couple of seconds like this-

For Smallest possible integer value of x:

From vertex 3: The weight of the edge (3,1) is 8. We can reach vertex 1 via vertex 2 in less than 8 cost i.e  if value of x is 0,1 or 2 than cost can be 5 (i.e 0+5), 6(i.e 1+5) or 7(i.e 2+5) respectively.

For Largest possible integer value of x:

From vertex 3 We can reach vertex 2 via vertex 0 in 13 cost. But we can reach vertex 2 via edge (3,2) if value of x is 12 (i.e largest possible).

Hence, Largest possible value of x =12.

Answer 3

x = 12

Comments

x=4

---

https://gateoverflow.in/?qa=blob&qa_blobid=2698428337827548934

---

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 4

if we see the existing paths between pair (3,4)
we see the one direct path which is x
now another path is 4-->2-->3 =cost=13
                                    4-->1-->3 =cost=13
                                    4-->1-->2-->3=cost=12(which is minimum possible cost between vertex 3 and 4)
therefore we can conclude that the maximum possible value at which there is at least one shortest path is there is 12 therefore x==12