Project ForgeConsider a network with 6 routers R1 to R6 connected with links having weights: R1-R2=6, R1-R3=3, R2-R3=2, R2-R4=7, R3-R5=9, R4-R5=1, R4-R6=8, R5-R6=4. All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?
Explanation
Computing all-pairs shortest paths: R1-R2's shortest route is via R3 (3+2=5), cheaper than the direct edge (6) — so the direct R1-R2 edge is never used. Similarly R4-R6's shortest route is via R5 (1+4=5), cheaper than the direct edge (8) — so the direct R4-R6 edge is never used either. Every other edge (R1-R3, R2-R3, R2-R4, R3-R5, R4-R5, R5-R6) appears in at least one shortest path. So exactly 2 links (R1-R2 and R4-R6) never carry data.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.