CODEWITHSUNDEEP
algorithmdirected-acyclic-graphslongest-path
user2253609
user2253609

Reputation: 97

Longest path in a Direct Acyclic Graph

How can I find the longest path in a DAG with no weights?

I know that the longest path from A to B can be found in linear time if the DAG is topologically sorted, but I need to find the longest path in all the graph. Is there any way faster than searching for the longest path between all pairs of vertices( which would be O(n^3))?

Upvotes: 1

Views: 1881

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

This is the same as finding the critical path.

There's an easy O(n) DP solution:

  • Topologically sort the vertices.
  • For each vertex i we will record earliest(i), the earliest possible start time (initially 0 for all vertices). Process each vertex i in topologically-sorted order, updating (increasing) earliest(j) for any successor vertex j of i whenever earliest(i) + length(i, j) > earliest(j).

After this is done, the maximum value of earliest(i) over all vertices will be the length of the critical path (longest path). You can construct a (there may in general be more than one) longest path by tracing backwards from this vertex, looking at its predecessors to see which of them could have produced it as a successor (i.e. which of them have earliest(i) + length(i, j) == earliest(j)), iterating until you hit a vertex with no predecessors.

Upvotes: 5

Related Questions