GATE2016-1-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

12 is correct answer.

---

Thanx. I used floyd warshal to solve it. Can u post ur solution?

---

@sushmita ji, How are you using Floyd Warshall. Can you please post your solution ?

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

best explanation

---

y can't 13 be the answer ?

In the above graph of jankyMurthy..label nodes 1=A 2=B 3=C and 4=D.

Now u can take path from C to D as direct edge with weight 13 or indirect from C to A(5) and A to D(8).. which is again 13...so why not 13 can be the maximum weight ?

---

A correction: 

The shortest distance between node 3 and node 4 is 12 (via node4, node1, node2, node3) or x (via direct path). So if you keep x=12, at least one shortest path between some pair of vertices will contain the edge with weight x.
 

If you consider the shortest path as 13 (5+8 or 8+5), then answer would be 13, which is not the case.

---

@nitesh Bcz from 3 -> 2 ->1-> 4 is a path with weight 12

---

Ya i got it,my bad..

thanks for pointing that path

---

Does this question use the concept of Floyd Warshal's algo?

---

By x=2 also gives at least one shortest path. So why not x=2?

---

Because the question asks for the largest possible integer value of x.

---

The answer needs editing here:

Shortest Path from 1 to 3 : 7 (1-2-3)

Shortest Path from 2 to 4 : 7 (2-1-4)

---

but $12$ does not ensure that it will be included in shortest path because

$3\rightarrow2 \rightarrow1\rightarrow4$ also gives a way of getting $12$.
Taking $x=11$ ensuring it will taken why we are taking $12$?

---

Hello saxena same thing perplexed me.

see this graph

Here if question is just same as our original question like "largest value of $w$ such that at least one shortest path b/w some pair of vertices will contain this edge with weight $w$"

So confusion is b/w $w=5$ or $w=6$. when $w=6$ then to reach vertex $2$ to vertex $3$ there are two shortest paths , either $2\rightarrow 1\rightarrow 3$ or $2\rightarrow 3$.

Now see questioner is asking like , 'i don't care if there are multiple shortest paths b/w some pair of vertices but at least one out of those must contain this edge with weight '$w$'. so in that way , if we have to tell maximum possible value of $w$ then it's $6$ in that case.

---

very well explained.

My doubt is: how to ensure that atleast 1 is guaranteed? like for x=12 it may still go thorugh other path 3-2-1-4 which is also 12? is it like if there are multiple long path and another direct path with same cost then Floud Warshall always choses the direct path during algo application?



as per above pic, the weights are initialized to the edge cost, now they are updated only when the other intermediate is smaller (not equal) than it.

so here even 12 will guarantee that x is chosen?

am i right?

---

Classic solution :)

---

The answer should be 11, right ??

---

precise explanation thanks;

---

Please correct your ans. It is right ans with mistakes in calculations. Shortest path from 3-4 is of length 12 and not 13(path being 3-2-1-4). fix this solution someone

---

While going from vertex 1 to 3 and taking path of 1-4-3 we get 5+x.Why does value of x in above mentioned ans is taken as,less than 3 and not equal to 3.

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

By mistake of not reading question correctly. they have mentioned atleast 1 shortest path must contain edge x. 12 and 13 are already there, so thought of 11 coming as shortest path. but 12 is enough. 12 is the answer

---

I can't understand.plz draw the graph.

---

why not 4.after 8 then two path 5 and x.so x=4

---

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?

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.

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.

Answer 6

x = 12

Comments

Explanation?

---

There already exist a path of  weight 12 from 4th node to 5th node. So i think it should be 11.

---

please see the explanation of answer given by me

---

x=4

---

https://gateoverflow.in/?qa=blob&qa_blobid=2698428337827548934

---

in the Qtn they have given a hint "at least one shortest path"

so there could be more number of shortest paths of equal weight. 11 will not be correct, becoz , then this path of weight 11 will be the ONLY shortest path. Hence we have to find a path of same least weight. so x will be only 12, and not any other value.

Answer 7

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.

Answer 8

We can create the following graph from the given matrix

if we want to make x be mandatorily incuded in at least one of the shortes path from C to D ...(I am leaving considering between other pair of vertices you can check other answers ....why it is not possible ..we will not be getting the maximum value of x in that way)

Then

the following paths are possible :

p1 : C-D (cost= x)

p2: C-B-A-D (cost =5+2+5 = 12)

p3 : C- B- D (cost = 5+8=13)

p3 cannot be the shortest path from C to D

if x = 13 then only p2 will be the shortest path from C to D

if x = 11 only p1 (containing x ) will be the shortest path from C to D

if x = 12 .the both p1(containing x ) and p2 will be the shortest paths from C to D i.e. there will be 2 shortest paths from C to D and one of them will contain x...this is what is asked by the question

 

Hence ans =12