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?
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 -∞).
Indeed, shortest path algorithms have trouble with negative numbers,
This is true for Dijkstra's Algorithm, but not for shortest path algorithms in general. The Bellman-Ford Algorithm can deal with negative edge weights, provided the graph does not contain negative cycles. However:
Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is not reachable from the source.
I’ll add an answer for shortest path problem specifically. The general problem with negative edges is described well in Jack’s answer.
Consider a graph G = (V, E) with edges of length l(e) ≤ 0 for each edge e ∈ E. Shortest path in G is the same as longest path in G' with l'(e) = - l(e) ≥ 0 ∀e ∈ E. Longest path problem is known to be NP-hard in general graphs. Though it can be solved in linear time in DAGs and other classes of graphs.
As cls answered, the problem is with negative cycles only and Bellman-Ford algorithm can cope with some edges being negative. But longest path algorithm must cope with cycles in the graph and Bellman-Ford cannot give a correct answer on graphs with negative cycles. Therefore Bellman-Ford algorithm can be used to compute the longest path only in graphs with no positive cycles. Mentioning, because that idea is obviously not uncommon.
