Let G = (V, E) be a directed graph with nodes v1, v2, . . . vn. We say that G is

Question

Let G = (V, E) be a directed graph with nodes v1, v2, . . . vn. We say that G is an ordered graph if it has the following properties. (i) 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 , vj ) with i < j. (ii) Each node except vn has at least one edge leaving it. That is, for every node vi , i = 1, 2, . . . , n ? 1, there is at least one edge of the form (vi , vj ). The length of a path is the number of edges in the path.

Given an ordered graph G, find the length of the longest path that begins at v1 and ends at vn. Use a dynamic programming approach. What is the time complexity of your solution?

Explanation / Answer

In given directed graph edges are connected from vi to vj, with i<j.

So there is no edge connecting j to i. Thus the graph is also acyclic.

Now find topological sort of the graph, apply following dynami programming approach

to find longest path v1 to vn:

For each vertex store akey value which is : key(v)=maximum value among (1+key) of all its children.

Finally key value of v1 stores required length of longest path.

Above algorithm runsO(V+E) time , because topological sorting takes O(V+E) time and key calculation takes O(V) time.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.