GATE IT 2005 | Question: 85a

Question

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updated interval, three tasks are performed.

1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as $1$. Otherwise, the cost is set to $∞$.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.

• A. $\overset{\text{Table for node A}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{-} &\text{-} \\\hline    \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{B} & \text{3} \\\hline \text{E}& \text{C} & \text{3} \\\hline  \text{F}& \text{C} & \text{4} \\\hline \end{array}}$
• B. $\overset{\text{Table for node C}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline    \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{-} & \text{-} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{E} & \text{1} \\\hline  \text{F}& \text{E} & \text{3} \\\hline \end{array}}$
• C. $\overset{\text{Table for node B}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline    \text{B}& \text{-} & \text{-} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{C} & \text{2} \\\hline  \text{F}& \text{D} & \text{2} \\\hline \end{array}}$
• D. $\overset{\text{Table for node D}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{B} &\text{3} \\\hline    \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{-} & \text{-} \\\hline \text{E}& \text{E} & \text{1} \\\hline  \text{F}& \text{F} & \text{1} \\\hline \end{array}}$

Comments

No need to make table for each router. Just use your intuition and see what is the length of  shortest path possible between each pair of routers and  try to match with the given options.

---

lets try to understand in hindi basically  phle Column me ye entry h ki apn kha ja rhe h means (at which node we are Going) second column me ye entry h Via which node  matlb phle vale coulmn ki entry pe jane ke liye konsa node lena hai third column is for how many cost now do it then its easy one only

---

Opt. A -  Incorrect becuz of 4th Row,  correct 4th row => D | C | 2  as we can reach from C in 2

Opt. B - Incorrect bucuz of 6th Row,  correct 6th row => F | D | 2  as we can reach from D in 2

Opt. C - All rows are correct, infact 5th row can also be written as => E | D | 2

Opt. D - Incorrect becuz of 1st Row, correct 1st row => A | B | 2   or   A | C | 2

Answer 1

$$\overset{\text{Table for Node A}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{-} &\text{-} \\\hline    \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{B} & \text{2} \\\hline \text{E}& \text{C} & \text{2} \\\hline  \text{F}& \text{C} & \text{3} \\\hline \end{array}} \quad 
\overset{\text{Table for Node D}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{B} &\text{2} \\\hline    \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{-} & \text{-} \\\hline \text{E}& \text{E} & \text{1} \\\hline  \text{F}& \text{F} & \text{1} \\\hline \end{array}}
\quad \overset{\text{Table for Node C}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline    \text{B}& \text{B} & \text{1} \\\hline \text{C}& \text{-} & \text{-} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{E} & \text{1} \\\hline  \text{F}& \text{D} & \text{2} \\\hline \end{array}}
\quad \overset{\text{Table for Node B}}{\begin{array}{|c|c|c|} \hline \text {A} & \text{A} &\text{1} \\\hline    \text{B}& \text{-} & \text{-} \\\hline \text{C}& \text{C} & \text{1} \\\hline \text{D}& \text{D} & \text{1} \\\hline \text{E}& \text{C} & \text{2} \\\hline  \text{F}& \text{D} & \text{2} \\\hline \end{array}}$$

Correct tables are as above. 

Only option C is matching.

Comments

i u have made a  mistake in table for node c where path to F costs only 2.

---

@Prashant.

Your table for node C is also matching along with node B.

In node C table, last row needs correction !!

---

@Pavan

Although distances are right but next HOP in the C's table may be different rt...?

Answer 2

Answer: C

A, B, D do not give the shortest distance. After stabilizing, distance of all nodes from a specific node should be minimum.

Comments

After stabilizing can it happen that there exists a better path but the node is not aware of.e.g here in table for c a better path to F exists using D.is it ok?

@Arjun Sir

---

stablizing means the algo will run for n-1 steps,  and there no possible way that a beeter path is left. its similar to bellman ford algo

Answer 3

after stabilizing ,the shortest path is given by option (C) but here some people might think option (B) as answer  but they are mistaken  as in the last row of option (b) although the distance from C to F via E is 3 units but its not the best path or shortest path since we have an alternate path from C to F via D with a distance of 2 units. so option (C) is right.

Answer 4

Correct option -

3)	Table for node B  A  A  1  B  -  -  C  C  1  D  D  1  E  C  2  F  D  2

Answer 5

Just a small observation : for the nodes  B, C, D   no one is on cost 3 in the graph so option B,D gone
 now node a has cost 3 only on node F but option a saying multiple cost 3 so option A gone
therefore ans c