I have exercise to find longest path in DAG and print it. There's no specified if edges can only be positive, though. The list is from greedy algorithms, so I think they assumed edge weights can be only positive, because I can't think of modification that would deal with negative edges. I believe there's no optimal structure when edges can be negative. Am I right?
There's described how to find longest path in DAG, but they mention nothing about negative edge weights. Is it so trivia to deduce that it doesn't matter if edges are negative or not and am I so stupid or is it much harder problem then?
Best Answer
If the graph is acyclic (the 'A' in DAG), then there are only finitely many paths at all, and certainly one of those will be longest.
The dynamic-programming algorithm sketched at the end of the notes you link to does in fact apply directly to DAGs with possibly negative weights. The argument that it works (i.e. that it in fact computes the total weight of the heaviest path ending at each node of the graph) does not depend on the weights being positive.
Of course you have to handle the possibility that the heaviest path is to do nothing because all incoming weights are too negative -- so instead of $\max_{(u,v)\in E} \{\cdots\}$ you should really have $\max \bigl[\{0\}\cup\{\cdots\mid (u,v)\in E\}\bigr]$. But the notes must already be implicitly assuming something like that in the positive case, because otherwise for an initial node they would be asking for a maximum taken over the empty set!
(The notes don't seem to be extremely carefully proofread anyway; for example the input to the last algorithm shouldn't be "Weighted DAG $G=(V,E)$" but "Weighted DAG $G=(V,E,w)$".)