in DS edited by
23,626 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 ___________.
in DS edited by
23.6k views

4 Comments

If you see the line “at least one shortest path between some pair of vertices” in question it means that there can be more than 1 shortest path between pair of vertices and out of that n shortest path at least one of them uses edge x. In that way 12 goes as the answer. If word guaranteed  is used in question then we might had to go with 11.

0
0
No Dipak you are not reading it in context I think, see they have said basically you choose the largest value of ‘x’, and then get shortest path between each vertex, (not in all possible ways you can get shortest path between each vertex) for that chosen value of ‘x’ , so that x will edge in some vertex shortest path, which in turn means means give me value of ‘x’ for which it is guaranteed to be used in shortest path between some pair of vertex of the graph
0
0
Revision of the single shortest Path NPTEL
https://youtu.be/VQqVDNCJ1jA
1
1

9 Answers

100 votes
100 votes
Best answer

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

4 Comments

because you will have multiple paths if the value of x is 12, so you cant guarantee which path is selected
0
0

@Sachin Mittal 1 Sir @Deepak Poonia Sir @Lakshman Bhaiya bhaiya Please edit the answer . 

The answer needs editing here:


Shortest Path from 1 to 3 is 7  . The path is (1-2-3)

Shortest Path from 2 to 4 is 7 . The path is (2-1-4)

0
0
By brute force method we can get solution easily
0
0
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

4 Comments

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

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 .

 
0
0
What if question ask for minimum value of X?
1
1
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...

2 Comments

edited by
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.
10
10

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

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

2 Comments

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

 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.

1
1
Answer:

Related questions