質問: 皆様のアイデアを頂戴したいです。 仕事上の目的で、下のような有向グラフの最長経路を求めたい と考えております。1から5までです。 実際のグラフはもっと複雑です。ですので総当たりは難しいです。 最初ダイクストラ法を用いようと考えましたが 1ダイクストラ法は最小経路を求めるので、そのままでは最長経路 が求められない。 2負の重みがある。 ため断念しました。 上手くこの問題をダイクストラ法で解く方法、あるいはダイクストラ法 に限らず解く方法はないでしょうか。![画像の説明をここに入力](https://i.stack.imgur.com/fsqlR.png)
回答: 皆様回答ありがとうございます。参考にさせていただきます。 問題を見直して、DAG化して最長経路に近そうな値を求めることにしました。