I read that Critical Path Method uses the longest path method with positive weights and it is used for scheduling a set of project activities (time values must be positive).

In my case I need to find the longest path in DAG with both positive and negative weights. What can I use this problem for? I need an example.

# Best How To :

Finding longest path in a DAG doesn't really "care" about only positive weights, it is done using Dynamic Programming (DP) by following the formula:

```
D(target) = 0
D(i) = max { D(j) + w(i,j) | for each edge (i,j) }
```

The above is finding `D(v)`

, which is the maximal length path that starts at `v`

and ends at the target.

By going over the nodes in reverse order of Topological Sort, it is done in `O(V+E)`

.

Note that the above doesn't really care if an edge is negative or positive, it's basically a brute force approach, that when implemented as DP, done more efficiently by not recalculating the same things multiple times.