GATE CSE 2016 | Set 1 | Question: 38

Question

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

Comments

Make weighted graph using matrix and it will be a complete matrix of size 4. From here this is a 10 sec question

---

Answer

The largest possible integer value of $x$ is 12.

---

Explanation

To find the largest value of $x$ such that the edge $(v_3, v_4)$ is part of at least one shortest path, we need to compare the direct edge weight $x$ with all other possible paths between vertex $v_3$ and $v_4$.

1. The Weight Matrix

The given matrix $W$ provides the weights of the edges between four vertices ($v_1, v_2, v_3, v_4$):

$$W = \begin{pmatrix} 0 & 2 & 8 & 5 \\ 2 & 0 & 5 & 8 \\ 8 & 5 & 0 & x \\ 5 & 8 & x & 0 \end{pmatrix}$$

From this matrix, we can list the edge weights:

• $w(v_1, v_2) = 2$

• $w(v_1, v_3) = 8$

• $w(v_1, v_4) = 5$

• $w(v_2, v_3) = 5$

• $w(v_2, v_4) = 8$

• $w(v_3, v_4) = x$

2. Analyzing Paths Between $v_3$ and $v_4$

The question asks for the largest $x$ where the edge $(v_3, v_4)$ is included in at least one shortest path. This means $x$ must be less than or equal to the weight of the shortest alternative path between $v_3$ and $v_4$.

Let's evaluate all alternative paths from $v_3$ to $v_4$:

• Path 1 ($v_3 \to v_1 \to v_4$): $8 + 5 = 13$

• Path 2 ($v_3 \to v_2 \to v_4$): $5 + 8 = 13$

• Path 3 ($v_3 \to v_2 \to v_1 \to v_4$): $5 + 2 + 5 = 12$

The shortest alternative path has a weight of 12.

3. Conclusion

For the direct edge $(v_3, v_4)$ to be considered a "shortest path," its weight $x$ must not exceed the shortest available alternative.

• If $x < 12$, the direct edge is the unique shortest path.

• If $x = 12$, there are two shortest paths (the direct edge and the path $v_3 \to v_2 \to v_1 \to v_4$).

• If $x > 12$, the direct edge is no longer a shortest path.

Since the question asks for the largest integer value that allows the edge to be part of at least one shortest path, the answer is $x = 12$.

 

---

the main thing of this question is how u understand "for which at least one shortest path between some pair of vertices will contain the edge with weight x" 

what is meant by more than one short path:

 i.e there exists more than one path which gives same short path cost 

in this above question suppose x=12 

 then with 12 two shorts paths exists between v3 and v4 that are 

1. v3 -> v2 ->  v1 -> v4 or reverse (becz it is unirected )

2.v3 -> v4  (becz it is unirected )

now v3->v4 also one possible shortpath (but not it is only one) 

so thats why 12 is best answer 

 

Answer 1

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

Comments

By brute force method we can get solution easily

---

 @Sachin Mittal 1 sir is there any shorter way to solve this one ?

---

Screenshot from Cormen
Why x = 12 is the correct answer
Suppose we run Dijkshra's algorithm with vertex $4$ as source-
4 will be extracted ( extract min as source is 0) all its edges will be relaxed
d(4,1)= 5
d(4,2)=8 
d(4,3)= 12
Now 1 will be extracted and all its edges will be relaxed
now we get 
d(4,2)= 7
d(4,3) = 12 ..(unchanged)

then we will extract 2 and relax its outgoing edges
Notice here that we wont relax the edge (2,3) because we relax if its only STRICTLY LESSER.

thus, shortest path from 4 to 3 will be 4->3 and cost is 12.
 

Answer 2

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

Comments

In question this line( at least one shortest path between some pair of vertices will contain the edge with weight xx) should not have written edges/edge instead of edge only ? Because shortest path may contain more than one edge and the weight of all edges have to be x .

 

---

What if question ask for minimum value of X?

---

If they ask for minimum then minimum value can be anything as question considers integers value can go to any negative value with no certainity

Answer 3

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

Comments

the shortest path between $c$ to $d$ from your dig is $c-b-a-d = 12.$
The ques is not that straight, and it says that for what largest value of $x$, at least one shortest path will contain $x$. If we take $x = 12$, there will be two shortest paths between $c$ and $d$, ie. $c-b-a-d$ and $c-d$ itself.so taking $x= 12$, "at least one shortest path between any pair of vertices" may belong to it.

---

you are being corrected : the shortest path between c and d is not 13 but 12 (c-b-a-d) if you don't consider x

Answer 4

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

Comments

why not considering 3-2-1-4 which is 12?

---

 Yeah, even that path is also the shortest path. But it is given that,

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

Between the pair of vertices 3 & 4, Path 3-2-1-4 is the shortest path with cost 12. But this path doesn't contain the edge with weight x. That's why we considered the path 3-4.

---

I would like to add,

"Here the shortest path between 3 and 4 without using edge x is

                                       12 

For edge (3,4) to be part of a shortest path, it must not be longer than this:

                                     x≤12

Hence, Largest integer value:

                                       12

Answer 5

x =12.

if you take x =13, then there is path between C and D -> C-B-A-D which is 12, so x=13 will not consider as shortest path.

now if you take 11, then it will be shortest path but not largest, when x=12 then then there is two path between D and C which is 12. Both are the shortest path. So, it is shortest path which is largest.

Comments

Thanks sir finally understood

---

should have been the best answer

Answer 6

Draw the graph by considering the values given in the matrix as:

                                                                           

We have to find the largest possible integer value of x for which at least one shortest path between some pair of vertices will contain the edge (3,2) that is x.

After we draw the graph we can find it in couple of seconds like this-

For Smallest possible integer value of x:

From vertex 3: The weight of the edge (3,1) is 8. We can reach vertex 1 via vertex 2 in less than 8 cost i.e  if value of x is 0,1 or 2 than cost can be 5 (i.e 0+5), 6(i.e 1+5) or 7(i.e 2+5) respectively.

For Largest possible integer value of x:

From vertex 3 We can reach vertex 2 via vertex 0 in 13 cost. But we can reach vertex 2 via edge (3,2) if value of x is 12 (i.e largest possible).

Hence, Largest possible value of x =12.