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 ___________
Thanx. I used floyd warshal to solve it. Can u post ur solution?

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

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

thanks for pointing that path
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.
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 .

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

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.
x = 12
Explanation?
There already exist a path of  weight 12 from 4th node to 5th node. So i think it should be 11.
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.