Asked by Kiran_Kumar | Textbook Reference: CLRS Algorithms
### Critical Warnings & Common Student Pitfalls Many students make simple mistakes when solving this type of problem in the exam pressure: 1. **Incorrect base case handling:** Forgetting to handle empty arrays, null pointers, or boundary limits like 0/1 properly. 2. **Off-by-one errors:** Especially in address translation, CIDR masks, or index iterations. 3. **Mismatched units:** Mixing up bits vs bytes, or Hertz vs seconds. Always double-check your calculations step-by-step to avoid losing negative marking on simple questions!
The Floyd-Warshall algorithm uses dynamic programming. For each step $k$, we decide if vertex $k$ should be an intermediate vertex on the shortest path from $i$ to $j$. - If vertex $k$ is **not** an intermediate vertex, then the shortest path uses only vertices in $\{1, 2, \dots, k-1\}$. Its weight is $d_{ij}^{(k-1)}$. - If vertex $k$ **is** an intermediate vertex, we can split the path into $i \to k$ and $k \to j$. Since intermediate vertices of these subpaths are only in $\{1, 2, \dots, k-1\}$, their weights are $d_{ik}^{(k-1)}$ and $d_{kj}^{(k-1)}$. Taking the minimum of these two cases gives: $d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)}, \; d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$ Option A is correct.
### Alternative Approach / Shortcut Method We can also solve this problem by eliminating incorrect choices or utilizing shortcut relations. For a GATE candidate, speed is as important as accuracy. Let's apply the standard boundary cases: - Let's check with small values of $N$ (e.g. $N=1, 2, 3$). - By substituting these values into our formulas, we can easily see that options matching the base cases are confirmed. This alternative proof validates our selected consensus solution!