GATE CS 2016 Set 1 Q38 — Graphs

Let the vertices of the graph be $1, 2, 3,$ and $4$. The edge with weight $x$ is between vertices $3$ and $4$, represented as $e = \{3, 4\}$.

For the edge $\{3, 4\}$ to be part of at least one shortest path between some pair of vertices, the direct edge $\{3, 4\}$ must be a shortest path between $3$ and $4$. This requires that the weight $x$ must be less than or equal to the length of the shortest alternative path between $3$ and $4$ that does not use the edge $\{3, 4\}$:

Let's find all alternative paths between $3$ and $4$ and their respective weights:

• Path $3 \to 1 \to 4$: weight $= W_{31} + W_{14} = 8 + 5 = 13$
• Path $3 \to 2 \to 4$: weight $= W_{32} + W_{24} = 5 + 8 = 13$
• Path $3 \to 2 \to 1 \to 4$: weight $= W_{32} + W_{21} + W_{14} = 5 + 2 + 5 = 12$

The shortest alternative path has a weight of $12$. Therefore, we must have $x \le 12$.

Thus, the largest possible integer value of $x$ is 12.