GATE 2016 CS (CS1) – 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 $\{3,4\}$ has weight $x$. It lies on a shortest path (between vertices 3 and 4, at least) as long as $x$ is not larger than the cost of every alternative route from 3 to 4.
Alternative routes from 3 to 4:
- $3\to1\to4$: $8+5=13$
- $3\to2\to4$: $5+8=13$
- $3\to2\to1\to4$: $5+2+5=12$
The cheapest alternative costs 12. The direct edge is then a shortest path (possibly tied) when $x\le12$. For $x=13$ the direct edge is longer than the route $3\to2\to1\to4$. For other pairs of vertices the edge $\{3,4\}$ does not help.
The largest integer $x$ is $\mathbf{12}$.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2016 CS (CS1) Q49
- GATE 2016 CS (CS1) Q50
- GATE 2017 CS (CS1) Q36
- GATE 2014 CS (CS1) Q13
- GATE 2014 CS (CS1) Q21
- GATE 2014 CS (CS1) Q23
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →