Consider the weighted undirected graph with 4 vertices, where the weight of…
2016
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 .
Attempted by 74 students.
Show answer & explanation
Correct answer: 12
Answer: 12
Explanation: Label the vertices 1, 2, 3, 4. The given edge weights are:
w(1,2) = 2, w(1,3) = 8, w(1,4) = 5
w(2,3) = 5, w(2,4) = 8
w(3,4) = x (this is the edge we are testing)
To decide the largest integer x for which the edge between vertices 3 and 4 lies on at least one shortest path, compare the direct edge weight x with the shortest path weight between 3 and 4 that avoids the direct edge.
Compute the alternative simple paths from 3 to 4 (not using the direct edge) and their weights:
3 → 1 → 4: 8 + 5 = 13
3 → 2 → 4: 5 + 8 = 13
3 → 2 → 1 → 4: 5 + 2 + 5 = 12
3 → 1 → 2 → 4: 8 + 2 + 8 = 18
The shortest alternative route from 3 to 4 that does not use the direct edge has weight 12 (via 3 → 2 → 1 → 4).
Therefore the direct edge between 3 and 4 will be part of a shortest path between some pair of vertices precisely when x ≤ 12. The largest integer x satisfying this is 12.
A video solution is available for this question — log in and enroll to watch it.