edited by
23,737 views
65 votes
65 votes
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 ___________.
edited by

9 Answers

Best answer
100 votes
100 votes

Let us list down the shortest edge between each pair of vertices $x,y$ in the graph

$$\begin{array}{|c|c|c|}\hline \textbf{x} & \textbf{y} & \textbf{shortest path from x to  y} \\\hline  \text{1} & \text{2} & \text{2} \\\hline   \text{1} & \text{3} & \text{there is a direct path from 1 to 3 of weight 8.We can also choose to go}\\ && \text{ via node 4 with total path weight $5+x.$ if $5+x<8(x<3)$ then shortest}\\&&\text{path is $5+x$ otherwise shortest path is the weight of the direct path}\\ && \text{which is 8} \\\hline  \text{1} & \text{4} & \text{5} \\\hline \text{2} & \text{3} & \text{5} \\\hline  \text{2} & \text{4} & \text{there is a direct path from 2 to 4 of weight 8. We can also choose to go}\\ && \text{via node 3 with total path weight}{ 5+x}\text{. If }{ 5+x<8(x<3)}\text{ the shortest}\\ && \text{path is 5+x. otherwise shortest path is the weight of the direct path}\\ && \text{which is 8} \\\hline  \text{3} & \text{4} & \text{We can chose to go through the direct path of weight x or via nodes 2, 1 }\\ && \text{to node 4 with weight } 5+2+5=12 \text{. If }{x<12}\text{ then we will chose x to be the shortest}\\&& \text{path otherwise $12$ is the shortest path} \ \\\hline \end{array}$$ 

  • Case 1: Let us say $x < 3$. Say $x = 2$.

When we put $x = 2$ the above table is modified as

$$\begin{array}{|c|c|c|}\hline \textbf{x} & \textbf{y} & \textbf{shortest path from x to y} \\\hline  \text{1} & \text{2} & \text{2} \\\hline   \text{1} & \text{3} & \text{7} \\\hline  \text{1} & \text{4} & \text{5} \\\hline \text{2} & \text{3} & \text{5} \\\hline  \text{2} & \text{4} & \text{7} \\\hline  \text{3} & \text{4} & \text{2 // Note that the shortest path between nodes $3$ and $4$ is $x =2$} \\\hline  \end{array}$$

  • Case 2: $3 \leq x < 13$. Let's say $x = 12$. The table is now modified as

$$\begin{array}{|c|c|c|}\hline \textbf{x} & \textbf{y} & \textbf{shortest path from x to y} \\\hline  \text{1} & \text{2} & \text{2} \\\hline   \text{1} & \text{3} & \text{8} \\\hline  \text{1} & \text{4} & \text{5} \\\hline \text{2} & \text{3} & \text{5} \\\hline  \text{2} & \text{4} & \text{8} \\\hline  \text{3} & \text{4} & \text{12 // Note that the shortest path between nodes $3$ and $4$ is $x=12$} \\ && \text{and one of the shortest path is the direct edge $x$} \\ \hline   \end{array}$$ 

Now the question asks you to find the largest possible integer value of $x$ such that shortest path between at least one pair of nodes in the graph is equal to $x.$ For values $x = 2,3,4,\ldots,12$ the shortest path between node $3$ and $4$ is equal to $x$.

The largest among this is $x = 12$. So the answer is $12$

PS:  If the question is modified as "The largest possible integer value of $x$, for which the shortest path between some pair of vertices is guaranteed to contain the edge with weight $x$ is"
then the answer will be $11.$

Correct Answer: $12.$

edited by
58 votes
58 votes
Answer is $x=12$.  Here, when we read the last sentence of the question, i.e the largest possible integer value of $x$. when $x=11$, the shortest path is an edge with weight $x$ only. But when $x=12$, there are $2$ shortest paths, and we can say that the edge with weight $x$ is also the shortest path. At least $1$ shortest path contain edge $x$. So the answer will be $12$.
edited by
24 votes
24 votes

ans is simple....if we want to get shortest path between c and d without x its 8+5=13 so to get the shortest path between c and d we can include weight 12 which is maximum...correct me if i am wrong...

15 votes
15 votes

For the people who didn't understand the above explanations ( although going through them again will make it clear) I'm putting in simple words.

We're asked to find value$'x'$ so that shortest path between any two vertices contains the edge with cost $'x'.$

Let us verify for the vertices $3$ and $4.$

To travel from vertex $3$ to vertex $4$: we have $3$ possible paths.

$1.$ Path $3-1-4$ with cost$=8+5=13$

$2.$ Path $3-2-4$ with cost$=5+8=13$

$3.$ Edge $3-4$ with cost$=x$

So, for the edge $3-4$ to be the shortest path between vertices $3$ and $4$, $x$ should be less than $13$.

Since we're asked to find the maximum value for $x$, the answer is $12.$

edited by
Answer:

Related questions

85 votes
85 votes
18 answers
4
Sandeep Singh asked Feb 12, 2016
35,051 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...