An example of finding the longest path in DAG with both positive and negative weights

Question

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.

Answer 1

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.