

非負の重み付き有効グラフに対しての最長経路問題がNP困難である事は存じ上げています。しかし、各辺の重みを-1倍したグラフに対し、ベルマンフォード法を用いて最短経路問題を解けば、必然的に最長経路問題も解けるような気がしたのですが何が問題なのでしょうか。


CC BY-SA 4.0
2022-11-30T17:10:59.737
92514
2022-12-01T07:35:20.003
2022-12-01T04:46:35.470
19110
55702
question
アルゴリズム 計算量
最長経路問題とベルマンフォード法について


NP 完全性が関係してくるような「最長経路問題」とは、重みつき有向グラフの最長の単純路（simple path、頂点が重複しない
path）を求める問題のことを指してらっしゃるのだと思います。一方ベルマン・フォード法を使うような「最短経路問題」では最短の路を求める問題を解いています。路ではなく単純路を求めることを踏まえると、単に辺の重みを
-1 倍するだけでは足りないと分かります。

また、もし最長の単純路を求めるという問題ではなく最長の路を求めるという問題を考えるのであれば、重みを -1
倍することで最短経路問題に帰着できます。この場合もとのグラフに始点から到達できる正閉路があるときは無限に長さを大きくできるので解が無いということになります。


CC BY-SA 4.0
2022-12-01T07:35:20.003
92517
2022-12-01T07:35:20.003
19110
92514
answer