Computing shortest path including specific edge

Question

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:

1. Node_4 → Node_2 → Node_3 $=$ cost $= 8+5=13$
2. Node_4 → Node_1 → Node_2 → Node_3 $=$ cost $= 5+2+5=12$
3. Node_4 → Node_3 $=$ cost $= x =$ maximum value should be less than $12 = 11$

Can you explain in formal way, please?

Answer 1

We observe the graph corresponding to the transition matrix $W$ is undirected, i.e. $w_{i,j} = w_{j,i}$ with $1\leq i,j\leq 4$ and the graph is also complete, i.e. each node is reachable in one step from each other node.

We denote the nodes of the graph with $\mathcal{N}=\{1,2,3,4\}$ according to the indices of the matrix \begin{align*} W=\begin{bmatrix} 0&2&8&5\\ 2&0&5&8\\ 8&5&0&x\\ 5&8&x&0\\ \end{bmatrix}=(w_{i,j})_{1\leq i,j\leq 4} \end{align*}

We now consider systematically the weights of all relevant paths $P_{i,j}$ from node $i$ to $j$ with $1\leq i<j\leq 4$. According to the properties of $W$ these are all paths of length $\leq 3$.

Assuming $x\in \mathbb{N}\backslash\{0\}\\$, we obtain \begin{align*} P_{1,2}:&\min \{w_{1,2},w_{1,3}+w_{3,2},w_{1,4}+w_{4,2},w_{1,3}+w_{3,4}+w_{4,2},w_{1,4}+w_{4,3}+w_{3,2}\}\\ &=\min\{2,8+5,5+8,8+x+8,5+x+5\}\\ &=2\\ P_{1,3}:&\min \{w_{1,3},w_{1,2}+w_{2,3},w_{1,4}+w_{4,3},w_{1,2}+w_{2,4}+w_{4,3},w_{1,4}+w_{4,2}+w_{2,3}\}\\ &=\min\{8,2+5,5+x,2+8+x,5+8+5\}\\ &=\min\{7,5+x\}\\ P_{1,4}:&\min \{w_{1,4},w_{1,2}+w_{2,4},w_{1,3}+w_{3,4},w_{1,2}+w_{2,3}+w_{3,4},w_{1,3}+w_{3,2}+w_{2,4}\}\\ &=\min\{5,2+8,8+x,2+5+x,8+5+8\}\\ &=5\\ \mathcal{P}_{2,3}:&\min \{w_{2,3},w_{2,1}+w_{1,3},w_{2,4}+w_{4,3},w_{2,1}+w_{1,4}+w_{4,3},w_{2,4}+w_{4,1}+w_{1,3}\}\\ &=\min\{5,2+8,8+x,2+5+x,8+5+8\}\\ &=5\\ \mathcal{P}_{2,4}:&\min \{w_{2,4},w_{2,1}+w_{1,4},w_{2,3}+w_{3,4},w_{2,1}+w_{1,3}+w_{3,4},w_{2,3}+w_{3,1}+w_{1,4}\}\\ &=\min\{8,2+5,5+x,2+8+x,5+8+5\}\\ &=\min\{7,5+x\}\\ \mathcal{P}_{3,4}:&\min \{w_{3,4},w_{3,1}+w_{1,4},w_{3,2}+w_{2,4},w_{3,1}+w_{1,2}+w_{2,4},w_{3,2}+w_{2,1}+w_{1,4}\}\\ &=\min\{x,8+5,5+8,8+2+8,5+2+5\}\\ &=\min\{x,12\}\\ \end{align*}

We observe the minimum weighted path from node $3$ to $4$ has weight $\min\{x,12\}$ and admits the largest value $x=12$ with respect to all other relevant paths.

Answer 2

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.$

Answer 3

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$.