GATE CSE 2010 | Question: 55

Question

Consider a network with $6$ routers $R1$ to $R6$ connected with links having weights as shown in the following diagram.

Suppose the weights of all unused links are changed to $2$ and the distance vector algorithm is used again until all routing tables stabilize. How many links will now remain unused?

• A. $0$
• B. $1$
• C. $2$
• D. $3$

 

Comments

Then R5-R6 will remain unused.

---

I hope this is correct

---

If there is a shortest link bw any two Routers then that link will definitely be there
for example bw R3 and R4 paths can be R3-R1-R2-R4 = 3+2+7 = 12  and  R3-R2-R4 =  2+7 = 9  so , R3-R2 will definitely be present

Answer 1

First we need to find which are the unused links in the graph
For that we need not make distance vector tables,
We can do this by simply looking into the graph or else DVT can also give the answer.
So, $R1-R2$ and $R4-R6$ will remain unused.

Now If We changed the unused links to value $2$.
$R5-R6$ will Now remain unused.

So, the correct answer is option B).

Comments

Answer would be zero instead of 1.

---

@kp1

No! R5---R6 edge is never present in any shortest path between any two pairs of nodes.

Hence B)1  is the correct answer.

---

@rohith1001 yes u r right. Actually in previous year book there is a misprint ( it is given cost of R5-- R6 link is 3) so if u take 3 then answer will be zero.. But in the actual question R5--R6 link is 4. Thus answer will be 1.

Answer 2

Only one link is not used

Comments

@pC  $R3 $ to $R6$ distance should be $11$  

---

Yes R3->R2->R4->R6

Answer 3

The links R1-R2  and R4-R6 will never be used for data transfer because there are shorter paths available in any case.
If those two link weights are changed to 2, now only one link ie R5-R6 will never be used.

Answer 4

Option-B

SImple reason for this.Use your intuition like below way

Find all the shortest path from each node to other and mark your visited edge .Then automatically in first searching u will find that only two edge are unused example edge R1---->R2 as well as R4---->R6.

When u change it into 2,Then again apply your intuition to find out shortest path from each node to other in this satuation u again find on link is unused.

Answer 5

Ans is B 

now

Answer 6

Please correct the question in your text book who thinks answer should be 0

Distance between R5 and R6 is 4 and not 3 as asked in gate 2010 please correct the question