5

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

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

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

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

上手くこの問題をダイクストラ法で解く方法、あるいはダイクストラ法
に限らず解く方法はないでしょうか。画像の説明をここに入力

3
  • 2
    途中にループがあるときは、最長経路は無限、つまりループを永遠に回るというケースもあり得ますが、それはどうするのでしょうか。例えば、上の図の場合、1から2に行くとして、1->4->3->5->4->3->5->... というケースが考えられます。一度通った経路は、二度と通らないなどの条件があるのでしょうか。
    – Hideki
    2018年9月24日 13:57
  • 2
    当たり前かも知れませんが、全ての重みに -1 を掛けて重みを逆転させた上での最短経路が最長経路だと思いますので、負の重みが使えるアルゴリズムでさえあれば、最短経路を求めるものとして紹介されているものでも、そのまま使えるのではないかと思います。 ちょっと調べると、「ベルマン-フォード法」が負の重みを扱えるようです。 ただ負の重みがあれば、 Hideki さんのコメントにある「ループを永遠に回るというケース」が最短経路になり得ますので、結局その点の考慮が必要ですね。
    – mjy
    2018年9月24日 14:36
  • にわかで仕込んだ知識ですがあれこれ。『ダイクストラ法は重み≧0かつ最短経路にしか使えない』(「ダイクストラ法で解く方法」はあり得ない。)『「ベルマン-フォード法」は重みの総和が負になるような閉路を含む場合解を出せない』(正負入れ替えると、重みの総和が正になる閉路を含む例示のグラフには使えない、そのような閉路が存在しないと言う条件が成立していない限り使えない)、『正閉路を避けるため同じ頂点を二度訪問してはいけないと言う制限をつけると、一般化された最長単純道問題となりNP完全、多項式時間で解けるようなアルゴリズムは見つからないと信じられている』(見つけたらフィールズ賞他数々の世界的数学賞を総なめにできるでしょう)。なんらかの現実的制約(「総当たり」と同じ計算量で良いからちょっとでも速く、とか)を付けられないとプログラミング上の課題とは言えないですね
    – OOPer
    2018年9月25日 1:30

2 件の回答 2

4

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

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

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

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

0

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。