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
def dfs ( node , adj , dp , vis ) : NEW_LINE INDENT vis [ node ] = True NEW_LINE for i in range ( 0 , len ( adj [ node ] ) ) : NEW_LINE INDENT if not vis [ adj [ node ] [ i ] ] : NEW_LINE INDENT dfs ( adj [ node ] [ i ] , adj , dp , vis ) NEW_LINE DEDENT dp [ node ] = max ( dp [ node ] , 1 + dp [ adj [ node ] [ i ] ] ) NEW_LINE DEDENT DEDENT def addEdge ( adj , u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE DEDENT def findLongestPath ( adj , n ) : NEW_LINE INDENT dp = [ 0 ] * ( n + 1 ) NEW_LINE vis = [ False ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if not vis [ i ] : NEW_LINE INDENT dfs ( i , adj , dp , vis ) NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans = max ( ans , dp [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE adj = [ [ ] for i in range ( n + 1 ) ] NEW_LINE addEdge ( adj , 1 , 2 ) NEW_LINE addEdge ( adj , 1 , 3 ) NEW_LINE addEdge ( adj , 3 , 2 ) NEW_LINE addEdge ( adj , 2 , 4 ) NEW_LINE addEdge ( adj , 3 , 4 ) NEW_LINE print ( findLongestPath ( adj , n ) ) NEW_LINE DEDENT