The GATE Grind

GATE 2016 CS (CS1) – Question 48

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

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

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →