edited by
23,739 views
65 votes
65 votes
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 ___________.
edited by

9 Answers

6 votes
6 votes

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.

3 votes
3 votes

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.

1 votes
1 votes
x = 12
1 votes
1 votes
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
Answer:

Related questions

85 votes
85 votes
18 answers
4
Sandeep Singh asked Feb 12, 2016
35,051 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...