Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.
Note: Length of a directed path is the number of edges in it.
Input: N = 4, M = 5
The directed path 1->3->2->4
Input: N = 5, M = 8
Simple Approach: A naive approach is to calculate the length of the longest path from every node using DFS.
The time complexity of this approach is O(N2).
Let dp[i] be the length of the longest path starting from the node i. Initially all positions of dp will be 0. We can call the DFS function from every node and traverse for all its children. The recursive formula will be:
dp[node] = max(dp[node], 1 + max(dp[child1], dp[child2], dp[child3]..))
At the end check for the maximum value in dp array, which will be the longest path in the DAG.
Below is the implementation of the above approach:
Time Complexity: O(N)
Auxiliary Space: O(N)
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.
- Longest Path in a Directed Acyclic Graph
- Longest Path in a Directed Acyclic Graph | Set 2
- Shortest Path in Directed Acyclic Graph
- Assign directions to edges so that the directed graph remains acyclic
- All Topological Sorts of a Directed Acyclic Graph
- Clone a Directed Acyclic Graph
- Minimum time taken by each job to be completed given by a Directed Acyclic Graph
- Convert the undirected graph into directed graph such that there is no path of length greater than 1
- Find if there is a path between two vertices in a directed graph
- Shortest path with exactly k edges in a directed and weighted graph
- Find if there is a path between two vertices in a directed graph | Set 2
- Shortest path with exactly k edges in a directed and weighted graph | Set 2
- Minimum Cost of Simple Path between two nodes in a Directed and Weighted Graph
- Path with minimum XOR sum of edges in a directed graph
- Shortest path in a directed graph by Dijkstra’s algorithm
- Minimum Cost Path in a directed graph via given set of intermediate nodes
- Convert undirected connected graph to strongly connected directed graph
- Calculate number of nodes between two vertices in an acyclic Graph by Disjoint Union method
- DFS for a n-ary tree (acyclic graph) represented as adjacency list
- Count ways to change direction of edges such that graph becomes acyclic
If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to email@example.com. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.