Dynamic Programming

Let G = (V,E) be a directed graph with nodes v ₁ ,...,v _n . We say that G is an ordered graph if it has the following properties. (i) Edges go from a node with a lower index to a node with a higher index. In other words, every directed edge has the form (v _i ,v _j ) with i < j. (ii) Each node with the exception of v n has at least one edge leaving it. In other words, for every node v i ,i = 1,2,...,n 1, there is at least one edge of the form (v _i ,v _j ). (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. Set a = v ₁ Set L = 0 While there is an edge out of node a Choose the edge (a,v _j ) for the smallest possible j Set a = v _j Increase L by 1 Return L as the length of the longest path In your example, say both what the correct answer is and what the algorithm above finds. (b) Give an efficient algorithm that takes an ordered graph G and returns the length of the longest path that begins at v ₁ and ends at v _n .