Optimal substructure Theorem. A subpath of a shortest path is a shortest path roof. Cut and paste c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.4 Optimal substructure Theorem. A subpath of a shortest path is a shortest path. Proof. Cut and paste: