Proof of claim d,i (m)=mingdik m-D)+aki) 1 edges Relaxation for k<1 to n do if d >da,+ ikki then d tda+a ≤m-1 edges Note: No negative-weight cycles implies c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.5 Proof of claim dij ( m ) = min k { dik (m–1) + akj } ii j j M k’s ≤ m – 1 edges ≤ m – 1 edge s ≤ m – 1 edges ≤ m – 1 edges Relaxation! for k ← 1 to n do if dij > dik + akj then dij ← dik + akj Note: No negative-weight cycles implies δ ( i, j) = dij (n–1) = dij ( n) = dij (n+1) = L