How to find Longest Path in a Directed Acyclic Graph in python

In this article, we here learn about the  how to longest path in a directed acyclic graph in python

A Directed Acyclic Graph(DAG) is a type of graph that has directed edges and contains no cycles.

Directed Edges: In Directed Acyclic Graph, each edge has a direction, meaning it goes from one vertex or node to another. This direction signifies a one-way relationship and dependency between the nodes.

Acyclic: It indicates that there are no cycles or closed loops within the graph. We cannot  traverse a sequence of directed edges and return to the same node.

Properties of Directed Acyclic Graph (DAG)

They are 4 important properties of the DAG

1. Reachability Relation
2. Transitive Closure
3. Transitive Reduction
4. Topological Ordering

5.     def solve(self, graph):
          ans = 0
          n = len(graph)
          table = [-1] * n
          def dfs(u):
             if table[u] != -1:
                return table[u]
             p_len = 0
             for v in graph[u]:
                p_len = max(p_len, 1 + dfs(v))
             table[u] = p_len
             return p_len
          for i in range(n):
             ans = max(ans, dfs(1))
          return ans
   ob = Solution()
   graph = [
      [1, 2],
      [3, 4],
      [],
      [4],
      [2],
   ]
   print(ob.solve(graph))

   output:- 4

In summary, Directed Acyclic Graphs are a fundamental concept of the graph theory with numerous practical applications. DAGs play a  important role in tasks, data flow analysis, dependency resolutions, and various other areas of computer science and engineering.

They help optimize processes, manage dependencies, and ensure efficient of tasks and jobs to be done

This is used major in DSA.

It helps a lot in finding the longest path .