Chapter 6 problem 3: Let G = (V, E) be a directed graph with nodes v1,..., Vn. We say that G is an ordered graph if it has the following properties.
(1) Each edge goes from a node with a lower index to a node with a higher index. That is, every
directed edge has the form (vi, vy) with i (ii) Each node except v, has at least one edge leaving it. That is, for every node
Vi, i = 1,2,..., 1 - 1, there is at least one edge of the form (Vi, v;). The length of a path is the
number of edges in it. The goal in this question is to solve the following problem (see Figure 6.29 for
an example)
Given an ordered graph G, find the length of the longest path that begins at vi and ends at un
(a) Show that the following algorithm does not correctly solve this problem, by giving an example
of an ordered graph on which it does not return the correct answer.

Figure 6.29 The correct answer for this ordered graph is 3: The longest path from v to
v, uses the three edges (U). Vs), (, Vs), and (V, Vs).
Set w=0
Set L = 0
While there is an edge out of the node w
Choose the edge (w, vy)
for which j is as small as possible
Set w = 0;
Increase L by 1
end while
Return L as the length of the longest path
In your example, say what the correct answer is and also what the algorithm above finds.
(b) Give an efficient algorithm that takes an ordered graph G and retums the length of the longest
path that begins at Uy and ends at vn (Again, the length of a path is the number of edges in the
path.)