Longest path in a directed Acyclic graph | Dynamic Programming | Java program to find the longest path in the DAG ; graph class ; Function to traverse the DAG and apply Dynamic Programming to find the longest path ; Mark as visited ; Traverse for all its children ; If not visited ; Store the max of the paths ; Function to add an edge ; Function that returns the longest path ; Dp array ; Visited array to know if the node has been visited previously or not ; Call DFS for every unvisited vertex ; Traverse and find the maximum of all dp [ i ] ; Driver code ; Example - 1
import java . util . ArrayList ; class Graph { int vertices ; ArrayList < Integer > edge [ ] ; Graph ( int vertices ) { this . vertices = vertices ; edge = new ArrayList [ vertices + 1 ] ; for ( int i = 0 ; i <= vertices ; i ++ ) { edge [ i ] = new ArrayList < > ( ) ; } } void dfs ( int node , ArrayList < Integer > adj [ ] , int dp [ ] , boolean visited [ ] ) { visited [ node ] = true ; for ( int i = 0 ; i < adj [ node ] . size ( ) ; i ++ ) { if ( ! visited [ adj [ node ] . get ( i ) ] ) dfs ( adj [ node ] . get ( i ) , adj , dp , visited ) ; dp [ node ] = Math . max ( dp [ node ] , 1 + dp [ adj [ node ] . get ( i ) ] ) ; } } void addEdge ( int a , int b ) { edge [ a ] . add ( b ) ; } int findLongestPath ( int n ) { ArrayList < Integer > adj [ ] = edge ; int [ ] dp = new int [ n + 1 ] ; boolean [ ] visited = new boolean [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) { if ( ! visited [ i ] ) dfs ( i , adj , dp , visited ) ; } int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { ans = Math . max ( ans , dp [ i ] ) ; } return ans ; } } public class Main { public static void main ( String [ ] args ) { int n = 5 ; Graph graph = new Graph ( n ) ; graph . addEdge ( 1 , 2 ) ; graph . addEdge ( 1 , 3 ) ; graph . addEdge ( 3 , 2 ) ; graph . addEdge ( 2 , 4 ) ; graph . addEdge ( 3 , 4 ) ; graph . findLongestPath ( n ) ; System . out . println ( graph . findLongestPath ( n ) ) ; } }