Answer: Floyd's algorithm

Question: When we initially wrote Floyd's algorithm we thought of the algorithm as using n+1 different matrices and included subscripts to distinguish them. Then I waved my hands and removed the subscripts. Why can we get away without the subscripts? Challenge problem: Suppose you were wrong on your last answer. What's another reason we can get away without subscripts? (CLR problem)

Answers:

1. In the kth iteration of the loop, we change each element to represent the shortest path between i and j using only the two endpoints plus the first k vertices. Before it used the k-1 vertices. The kth row and column of the matrix, then, will not change, since the two vertex sets are the same (the path already used the kth vertex since it is an endpoint).
2. Even if it did change, every entry still represents a valid path. The semantic meaning of the entry would change slightly: it now holds a path length that is at most (before it was exactly) the length of the shortest path between i and j using the first k vertices. This doesn't really hurt the algorithm.