algorithm - ほとんどのグラフアルゴリズムが負の数にそれほど簡単に適応しないのはなぜですか？

Question

アルゴリズム設計マニュアルには次のように書かれています。

ほとんどのグラフアルゴリズムは、負の数にそれほど簡単には適応しません。実際、最短経路アルゴリズムには負の数の問題があり、この手法を使用して可能な限り最長の経路を生成することはありません。

しかし、なぜ？元の重みの前に負の数を追加するだけ-で、重みを含むほとんどのグラフの問題は同等に処理できると思いますよね？

Answer 1

Answer 2

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.

Answer 3

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.