Project ForgeConsider the weighted undirected graph with 4 vertices 1,2,3,4, where the weight of edge {i,j} is given by the entry Wij in the matrix:
W = [[0,2,8,5],[2,0,5,8],[8,5,0,x],[5,8,x,0]]
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 ____.
Explanation
The edge in question connects vertices 3 and 4, with weight x. Its only competing alternate routes are: 3-1-4 (8+5=13), 3-2-4 (5+8=13), 3-1-2-4 (8+2+8=18), and 3-2-1-4 (5+2+5=12) — the cheapest alternative is 12. For the direct edge (weight x) to be part of SOME shortest path between 3 and 4, it must be no worse than the best alternative, i.e. x ≤ 12. At x=12 it ties with the 3-2-1-4 path, so it IS one of the (tied) shortest paths. The largest valid integer is 12.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.