The solution for this question is wrong. For my Algorithm course, I was asked to provide a counterexample to show that the given equation is wrong. And I think, my solution provides enough insight.
In the given example, you can see that no path exists between i and j for k=2, and k=3. Therefore d^(k-1)_i,j and d^(k)_i,j both are equal to infinity. And the correct pi value must be NIL. But if we were to follow the equation given in the recurrence, we get pi^(k)_i,j = pi^(k)_3,j = 3 instead.
The solution for this question is wrong. For my Algorithm course, I was asked to provide a counterexample to show that the given equation is wrong. And I think, my solution provides enough insight.
In the given example, you can see that no path exists between i and j for k=2, and k=3. Therefore d^(k-1)_i,j and d^(k)_i,j both are equal to infinity. And the correct pi value must be NIL. But if we were to follow the equation given in the recurrence, we get pi^(k)_i,j = pi^(k)_3,j = 3 instead.