GATE 2016 CS – Question 48
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 12
Explanation
The edge between vertices 3 and 4 has weight $x$. The other routes from 3 to 4 are $3 \to 2 \to 4$ with weight $5 + 8 = 13$, $3 \to 1 \to 4$ with weight $8 + 5 = 13$, and $3 \to 2 \to 1 \to 4$ with weight $5 + 2 + 5 = 12$. The direct edge is on a shortest path as long as $x \leq 12$, so the largest integer is 12.