Sightseeing in an Arbitrary Directed Graph
Let’s look at the longest path problem in an arbitrary directed graph before relating it to the problem of finding the longest common subsequence.
We'll cover the following
In reality, the streets in Midtown Manhattan don’t form a perfect rectangular grid because Broadway Avenue cuts diagonally across the grid, but the network of streets can still be represented by a directed graph. In fact, the Manhattan Tourist Problem is just a special case of the more general problem of finding the longest path in an arbitrary directed graph, such as the ones in figure below.
Get hands-on with 1400+ tech skills courses.