MA415 HOMEWORK #5
Due Monday, March 27
Let W be the matrix of edges weights for a simple graph; i.e., equals the weight of edge ij. We define for and if ij is not an edge. Assume for all i,j. Prove by induction on n that entry i,j of equals the weight of a minimum weight path from i to j that uses no more than n edges, where the power is computed according to the new matrix product rule. Then use this to prove that when , the i,j entry of equals the weight of the minimum weight path from i to j. Finally, by repeated squaring, use this method to solve Problem 9 in Section 6.1.