Recall that Floyd-Warshall relies on dynamic programming to build solutions for all pairs of vertices by considering intermediate vertices one by one. How does this approach ensure that the optimal substructure property holds for the algorithm?

Consider a shortest path between two vertices *u* and *v* that includes an intermediate vertex *k*. If you remove *k* from this path, the remaining path must still be the shortest path between *u* and *v* without *k*. How does this observation relate to the optimal substructure of the Floyd-Warshall algorithm?

Prove that the Floyd-Warshall algorithm correctly computes the shortest paths by induction on the number of intermediate vertices considered. Specifically, show that if the algorithm correctly computes shortest paths using the first *k* vertices as intermediates, then it also correctly computes shortest paths using the first *k+1* vertices as intermediates.