Why most graph algorithms do not adapt so easily to negative numbers?

Question

The Algorithm Design Manual says:

Most graph algorithms do not adapt so easily to negative numbers. Indeed, shortest path algorithms have trouble with negative numbers, and certainly do not generate the longest possible path using this technique.

But why? When we just add a negative - in front of original weight, I think most graph problems involving weight can be dealt equally, right?

Answer 1

Because when you are considering the minimum or maximum cost of a path you always end up considering the sum of all single steps.

And since many of these algorithms work locally by choosing best approach step by step (with step of different magnitude, of course), having negative weights would just generate cycles or false positives.

Having a negative weight implies that the cost of a path can decrease in the future, that's why it creates problems: you could not exclude paths from a list of potential good paths even after reaching a point in which the path up to now is more expensive than the other because you could find edges with negative weight which change the situation.

Just as an example: if you have two nodes connected mutually by two edges of weight 1 and -2 you could create a cycle between them to determine a path with arbitrary low cost (even -∞).