Longest path in a directed Acyclic graph | Dynamic Programming | 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
function dfs ( node , adj , dp , vis ) { vis [ node ] = true ; for ( var i = 0 ; i < adj [ node ] . length ; i ++ ) { if ( ! vis [ adj [ node ] [ i ] ] ) dfs ( adj [ node ] [ i ] , adj , dp , vis ) ; dp [ node ] = Math . max ( dp [ node ] , 1 + dp [ adj [ node ] [ i ] ] ) ; } } function addEdge ( adj , u , v ) { adj [ u ] . push ( v ) ; } function findLongestPath ( adj , n ) { var dp = Array ( n + 1 ) . fill ( 0 ) ; var vis = Array ( n + 1 ) . fill ( false ) ; for ( var i = 1 ; i <= n ; i ++ ) { if ( ! vis [ i ] ) dfs ( i , adj , dp , vis ) ; } var ans = 0 ; for ( var i = 1 ; i <= n ; i ++ ) { ans = Math . max ( ans , dp [ i ] ) ; } return ans ; } var n = 5 ; var adj = Array . from ( Array ( n + 1 ) , ( ) => Array ( ) ) ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 1 , 3 ) ; addEdge ( adj , 3 , 2 ) ; addEdge ( adj , 2 , 4 ) ; addEdge ( adj , 3 , 4 ) ; document . write ( findLongestPath ( adj , n ) ) ;