# Longest Path in a Directed Acyclic Graph with weight

### 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

```
Author: