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