The optimal substructure property can be used to prove the following interesting property of the solution to single-source shortest-path problems.
We can always arrange the solution in a tree, so the shortest path to v involves following a shortest path to u and then taking the edge (u,v). The set of such edges forms a shortest path tree.
Example...
Proof?
