

皆様のアイデアを頂戴したいです。

仕事上の目的で、下のような有向グラフの最長経路を求めたい  
と考えております。①から⑤までです。

実際のグラフはもっと複雑です。ですので総当たりは難しいです。

最初ダイクストラ法を用いようと考えましたが  
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路  
が求められない。  
②負の重みがある。  
ため断念しました。

上手くこの問題をダイクストラ法で解く方法、あるいはダイクストラ法  
に限らず解く方法はないでしょうか。[![画像の説明をここに入力](https://i.stack.imgur.com/fsqlR.png)](https://i.stack.imgur.com/fsqlR.png)


CC BY-SA 4.0
2018-09-24T12:04:45.443
48677
2018-10-02T15:06:14.493
30222
question
アルゴリズム
負の重みを含んだ最長経路の求め方


<https://en.wikipedia.org/wiki/Longest_path_problem>

最長経路問題は、たとえ負の重みがなくても、一般的に NP 困難なので、総当たりするぐらいしか解がないかと思います。

いくつか、特殊なケースの最長経路問題(例えばループが存在しないグラフとか)であるならば、NP困難性を回避する手法は見つかっている様子ですが(mjy
さんのおっしゃる、重みの正負をひっくり返したグラフで解く)、今回のようなグラフについては、すくなくともこのグラフにおいては、そのような性質はなさそうだと思っています。

実際に仕事で扱うとしたら、最長経路問題を解かないで済むような方法をどうにかして考える、しかないと思っています。


CC BY-SA 4.0
2018-09-25T04:05:04.807
48689
2018-09-25T04:14:10.857
2018-09-25T04:14:10.857
754
754
48677
answer


皆様回答ありがとうございます。参考にさせていただきます。  
問題を見直して、DAG化して最長経路に近そうな値を求めることにしました。


CC BY-SA 4.0
2018-10-02T15:06:14.493
48907
2018-10-02T15:06:14.493
30222
48677
answer