Longest Path in a Directed Acyclic Graph with weight
Longest Path in a DAG represents minimum numbers of steps to list all vertices in group.
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: LongestPathInDAGWithWeight.java
Output:
0 -> [1(5), 2(3)] 1 -> [3(6), 2(2)] 2 -> [4(4), 5(2), 3(7)] 3 -> [5(1), 4(-1)] 4 -> [5(-2)] 5 -> [] Vertex (0) -- distance = -2147483648 Vertex (1) -- distance = 0 Vertex (2) -- distance = 2 Vertex (3) -- distance = 9 Vertex (4) -- distance = 8 Vertex (5) -- distance = 10