# Longest Path in a Directed Acyclic Graph

### Longest Path in a Directed Acyclic Graph

Equivalent to finding longest path in the DAG

• If inDegree (j) = 0 then, longest_path_to(j) = 0
• If InDegree (k) > 0 then, longest_path_to(k) is 1 + max{longest_path_to(j)} among all incoming neighbours j to k
• To compute longest_path_to(k)
• Need longest_path_to(j) for all incoming neighbours of k
• If j is an incoming neighbour (j,k) in E
• j is enumerated before k in topological order
• Hence, compute longest_path_to(i) in topological order
• Let i1, i2, …. in be topological ordering of V
• All the neighbours of ik appears before it in this list
• From left to right, compute longest_path_to(ik) as 1 + max{longest_path_to(ij)}
among all incoming neighbours ij to ik
• Can combine this calculation with topological sort

Latest Source Code:
Github: LongestPathInDAG.java

Output:

``` 0 -> [2, 3, 4]
1 -> [2, 7]
2 -> [5]
3 -> [5, 7]
4 -> [7]
5 -> [6]
6 -> [7]
7 -> []

Vertex(0) longest path = 0
Vertex(1) longest path = 0
Vertex(2) longest path = 2
Vertex(3) longest path = 1
Vertex(4) longest path = 1
Vertex(5) longest path = 2
Vertex(6) longest path = 1
Vertex(7) longest path = 4
```
Author: