Consider a directed graph G, and assume that instead of shortest paths we want to compute longest paths. Longest paths are defined in the natural way, i.e. the longest path from u to v is the path of maximum weight among all possible paths from u to v. Note that if the graph contains a positive cycle, then longest paths are not well defined (for the same reason that shortest paths are not well defined when the graph has a negative cycle). So what we mean is the longest simple path, (a path is called simple if it contains no vertex more than once).

Show that the the longest simple path problem does not have optimal substructure by coming up with a small graph that provides a counterexample.