540 views

In a LAN, $n^2$ routers are connected in an $n \times n$ mesh such that $R(i, j)$ represents a router in the $i$-th row and $j$-th column of the mesh.

1. Find how many distinct shortest paths exist between two routers $R(i_1, j_1)$ and $R(i_2, j_2) \: (1 \leq i_1, j_1, i_2, j_2 \leq n)$. Two paths are distinct if they differ in at least one link.
2. At most how many of these distinct shortest paths will be node disjoint, i.e., with no common node except the source and the destination? Justify your answer.

1. $\frac{(|j_1-j_2|+|i_1-i_2|)!}{(|j_1-j_2|)! (|i_1-i_2|)!}$

2. 2

by