皆様のアイデアを頂戴したいです。
仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。
実際のグラフはもっと複雑です。
最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。
上手くこの問題をダイクストラ法で解く方法、あるいはダイクストラ法
に限らず解く方法はないでしょうか。
最長経路問題は一般にNP-hardです。ダイクストラ法では解けないと思います。頂点数、辺数は具体的にどのぐらいか、何か別の制約はないのか(例えば、1辺の最大長が決まっているとか、小数点第3位以下は常に0とか)、どのぐらいの時間で求めたいのかを書いた方が良いと思います。
同一頂点を複数回含むような経路は考えますか?
早速の回答ありがとうございます。制約について、1辺は3~-3の間です。同一頂点を複数回含むような経路は考えておらず、できれば一筆書きで行きたいです。
頂点数はどのくらいですか?
19点です。
それはすごく小さいですね。辺の数はどのくらいですか?
81×2=162です。
同一頂点を複数回含まないようなパスのみを考えるのなら、dp[ i ][ s ] = 頂点集合sに含まれる頂点のみをたどって頂点 i に到達する最長経路の長さという配列を用意して、動的計画法をすると、始点sを固定したときの各頂点への最長経路が1秒ぐらいで求まると思います。
状態数が2^19 * 19個あり、各状態について、遷移が各状態について19個あるので、2^19 * 19 * 19 = 189267968回ぐらいの計算ですね
回答ありがとうございます。しかしながら、当方こういったアルゴリズムなどについてはほとんど初心者でございまして、できれば類似問題や参考になる問題などを例示していただけるとありがたいです。わがままで申し訳ないですがよろしくお願いします。