200px|thumb|Figure 1. Finding the shortest path using optimal substructure. Numbers represent the length of the path; straight lines indicate single [[Edge (graph theory)|edges, wavy lines indicate shortest paths, i.e., there might be other vertices that are not shown here.]]
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.
Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step.