How to find Longest Path in a Directed Acyclic Graph in Python?

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.

The time complexity of this approach is O(N2).

Efficient Approach: An efficient approach is to use Dynamic programming and DFS together to find the longest path in the graph.

def dfs(node, adj, dp, vis):

    vis[node] = True

    for i in range(0, len(adj[node])):  


        if not vis[adj[node][i]]:

            dfs(adj[node][i], adj, dp, vis) 

        dp[node] = max(dp[node], 1 + dp[adj[node][i]]) 

def addEdge(adj, u, v): 

  

    adj[u].append(v) 

def findLongestPath(adj, n): 

    dp = [0] * (n + 1) 

    vis = [False] * (n + 1)

    for i in range(1, n + 1):  

        if not vis[i]: 

            dfs(i, adj, dp, vis) 

      

    ans = 0

    for i in range(1, n + 1):  

        ans = max(ans, dp[i]) 

      

    return ans 


if _name_ == "_main_": 

  

    n = 6

    adj = [[] for i in range(n + 1)]

   

    addEdge(adj, 1, 4) 

    addEdge(adj, 1, 2) 

    addEdge(adj, 3, 2) 

    addEdge(adj, 2, 3) 

    addEdge(adj, 2, 4) 

   

    print(findLongestPath(adj, n))

 

Let dp[i] be the length of the longest path  starting from the node i. Initially all positions of dp will be 0.

Output:

3

3