ISI2014-PCB-CS-6b

Question

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.

Answer 1

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

2. 2

Answer 2

For the first part of the question, the number of distinct shortest paths between two routers R(1,1) and R(i2, j2) is equal to the number of possible combinations of links that can be taken to go from R(1,1) to R(i2, j2).

Since the routers are connected in a mesh, the shortest path will always consist of i2 - 1 links in the vertical direction and j2 - 1 links in the horizontal direction (assuming that i2 and j2 are both greater than 1; otherwise, the number of links in the path will be different).

Therefore, the total number of distinct shortest paths is equal to the number of ways in which these i2 - 1 vertical links and j2 - 1 horizontal links can be combined, which is equal to (i2 - 1)! * (j2 - 1)!

For the second part of the question, the maximum number of node-disjoint shortest paths between R(1,1) and R(i2, j2) is equal to the minimum of (i2 - 1) and (j2 - 1). This is because each node-disjoint path must use a different set of links in the mesh, and the maximum number of links that can be used in the mesh is limited by the number of links in the smallest dimension of the mesh (i.e., either the number of rows or the number of columns).

For example, if i2 is greater than j2, then the maximum number of node-disjoint shortest paths is equal to j2 - 1, because each path must use a different set of j2 - 1 horizontal links. If i2 is less than j2, then the maximum number of node-disjoint shortest paths is equal to i2 - 1, because each path must use a different set of i2 - 1 vertical links.

Therefore, the maximum number of node-disjoint shortest paths is equal to the minimum of (i2 - 1) and (j2 - 1).