Computing shortest path including specific edge Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i, j\}$ is given by the entry $W_{i, j}$ 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 ______?

My attempt:
Somewhere, answer is give $12$, and somewhere is $10$. According to me answer is $11$. Since, if we try to reach node_4 to node_3. There are three possible ways:


*

*Node_4 → Node_2 → Node_3 $=$ cost $= 8+5=13$

*Node_4 → Node_1 → Node_2 → Node_3 $=$ cost $= 5+2+5=12$

*Node_4 → Node_3 $=$ cost $= x =$ maximum value should be less than $12 = 11$



Can you explain in formal way, please?

 A: 
So between node 3 & 4, there are 5 paths,
$4->1->3 = 13$
$4->2->3 = 13$
$4->1->2->3 = 12$
$4->2->1->3 = 18$
$4->3 = x$
Clearly $X_{max} = 11.$
A: The answer is $12$.

Excluding the edge labeled $x$, the shortest paths are 
$AB=2$, $AC=7$, $AD=5$, $BC=5$, $BD=7$, and $CD=12$.
The main theoretical ingredient of this problem is that 
the lengths of the shortest paths can only decrease (or remain equal)
if we add a new edge.
The most promising is the longest shortest path $CD=12$.
Clearly, if we set $x=12$ on the edge connecting $C$ and $D$,
there will be two shortests paths, one simply $C-D$ and the other $C-B-A-D$, both of length $12$. So, if $x \le 12$ there will be at least one shortest path passing through $x$, as requested.
It is easy to see that a larger $x$ (say, $13$) can't be used, because all the existing shortest paths are already smaller of equal to $12$.
I think that the only confusion that can arise in this problem depends on misreading the question.
The question ask for "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$".
So, at least one shortest path, not every shortest path.  If it was every shortest path the answer would have been $11$, because we had to "beat" the shortest path $C-B-A-D=12$, but since the question asks for at least one among the shortest paths, then the answer is $12$, because having two shortest paths of length $12$ is fine, since one contains the edge $x$.
