Optimal Substructure Property

Because a shortest path is made up of other shortest paths (how many on a path of length n?), we say that the shortest-path problem exhibits the optimal substructure property.

How would you prove it?

Although it might seem backwardsly useful, we actually depend on this property quite a bit when finding shortest paths.


next up previous
Next: Shortest Path Tree Up: SHORTEST PATH PROBLEM Previous: Some Properties of Shortest