皆様のアイデアを頂戴したいです。
仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。①から⑤までです。
実際のグラフはもっと複雑です。ですので総当たりは難しいです。
最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。
皆様のアイデアを頂戴したいです。
仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。①から⑤までです。
実際のグラフはもっと複雑です。ですので総当たりは難しいです。
最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。
https://en.wikipedia.org/wiki/Longest_path_problem
最長経路問題は、たとえ負の重みがなくても、一般的に NP 困難なので、総当たりするぐらいしか解がないかと思います。
いくつか、特殊なケースの最長経路問題(例えばループが存在しないグラフとか)であるならば、NP困難性を回避する手法は見つかっている様子ですが(mjy さんのおっしゃる、重みの正負をひっくり返したグラフで解く)、今回のようなグラフについては、すくなくともこのグラフにおいては、そのような性質はなさそうだと思っています。
実際に仕事で扱うとしたら、最長経路問題を解かないで済むような方法をどうにかして考える、しかないと思っています。