Dynamic programming Consider the n x n adjacency matrix A=(a of the digraph, and define di m)=weight of a shortest path from i to that uses at most m edges Claim We have fo if i=j loo if i≠ and for m=1.2.. n-1 di(m)=mink dik (m-1)+ c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.4 Dynamic programming Consider the n × n adjacency matrix A = (aij) of the digraph, and define dij(0) = 0 if i = j, ∞ if i ≠ j; Claim: We have and for m = 1, 2, …, n – 1, dij(m) = mink{dik(m–1) + akj }. dij(m) = weight of a shortest path from i to j that uses at most m edges