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