A directed graph is simply an abstraction of a network of one-way roads between a set of cities. When one travels in such a network, one may return to the starting point. In this chapter, we are interested in special networks that exclude the possibility of ever returning to the starting point or to any city we have already visited. We refer to a network as acyclic.
Suppose we are traveling in an acyclic network of one-way roads. By definition, on each trip, we may visit each city at most once. A very natural question that arises is; what is the maximum number of cities we can visit? In this chapter, we present a simple and efficient algorithm that finds the longest sequence of cities we can visit in the special ...