Longest path in a directed Acyclic graph | Dynamic Programming | C ++ program to find the longest path in the DAG ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int node , vector < int > adj [ ] , int dp [ ] , bool vis [ ] ) { vis [ node ] = true ; for ( int i = 0 ; i < adj [ node ] . size ( ) ; i ++ ) { if ( ! vis [ adj [ node ] [ i ] ] ) dfs ( adj [ node ] [ i ] , adj , dp , vis ) ; dp [ node ] = max ( dp [ node ] , 1 + dp [ adj [ node ] [ i ] ] ) ; } } void addEdge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; } int findLongestPath ( vector < int > adj [ ] , int n ) { int dp [ n + 1 ] ; memset ( dp , 0 , sizeof dp ) ; bool vis [ n + 1 ] ; memset ( vis , false , sizeof vis ) ; for ( int i = 1 ; i <= n ; i ++ ) { if ( ! vis [ i ] ) dfs ( i , adj , dp , vis ) ; } int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { ans = max ( ans , dp [ i ] ) ; } return ans ; } int main ( ) { int n = 5 ; vector < int > adj [ n + 1 ] ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 1 , 3 ) ; addEdge ( adj , 3 , 2 ) ; addEdge ( adj , 2 , 4 ) ; addEdge ( adj , 3 , 4 ) ; cout << findLongestPath ( adj , n ) ; return 0 ; }