グラフの最長パスの求め方

質問

グラフの最長パスを求めるアルゴリズムにはどのようなものがあるのでしょうか。

例えば、以下のようなグラフであれば、最長パスは６になります。

・－・－・－・－・
　　|　　|
　　・－・

また、以下のようなグラフの場合、
最長パスは７として計算したいです。

・－・－・－・
　／　＼
・－・－・
※　下の三角形は、上の左から２番目のノードにくっついています。

最短パスを求めるアルゴリズムはいくつかありましたが、
最長パスを求めるアルゴリズムは見つけられませんでした。
何かアルゴリズム名などのキーワードはありますか。

回答No.4

Tacosan

グラフ理論ではいろんな言葉がごちゃごちゃに使われている傾向があるので「一般的」という言葉をむやみに使わない方がいいと思います＞#3. 同じ概念を異なる言葉で表現していたり, 逆に同じ言葉で異なるものを意味していたりすることはよくあるので....

「ひたすらパスを作って最長のものをおぼえる」だけでアルゴリズムにはなるんだけど.

お礼

回答ありがとうございます。

> 「ひたすらパスを作って最長のものをおぼえる」だけでアルゴリズムにはなるんだけど.

確かにそうですね。
最初のアルゴリズムとしてはこれを使ってみようと思います。
処理時間を実測してみて、ちょっと実用に耐えられないようなら他のアルゴリズムを検討してみます。

それから、コメントありがとうございます。

回答No.3

graphaffine

#2の補足は一般的に言うパスには成っていません。あなたのパスの定義は何でしょう。

>パスの意味が分かってるのかな。
これは無視ですか。

お礼

補足の通りです。

補足

元々の質問を整理しますが、

・－・－・－・
　／　＼
・－・－・

上記のようなグラフの場合、

　　１　６　７
　・－・－・－・
　２／　＼５
　・－・－・
　　３　４

このようにカウントして最大パス長は７として計算したいということです。

==========

普段はわざわざこのようなことは書かないのですが、
回答いただけたのも何かの縁ですので。。。

質問を読んでいただいて理解されているとは思いますが、
この質問は最大パス長の定義を問うものではありません。
前述したとおりの方法で最大パス長を求める方法に関する質問です。
それは質問自体と、No.2の補足で説明した通りです。

ですので、

> > パスの意味が分かってるのかな。
> これは無視ですか。

お礼のコメントを無視したわけではなく、どのように計算するのか具体例を示すことで、
最大パス長（この例では７）の求め方を示したつもりです。

グラフ理論における典型的な最大パス長が、例えばループがないものとかその他のどのようなものであれ、
今回の質問に関してはまったく興味がありません。
質問や補足に記載の方法で最大パス長を求めるためにはどうしたらいいか知りたいのです。

どのように最大パス長を計算すればよいか、アルゴリズムやあるいは検索キーワードを教えていただけませんか。

それでもなお、質問自体に回答せず、
「その定義は一般的な最大パス長ではない」とか「正しい最大パス長の定義を理解していますか？」とか、
「質問文に『最大パス長』という文言が含まれているのに勝手な定義をしないでください」とおっしゃるのであれば、
それはお互い工数の無駄になるだけですので、私の質問に回答していただかなくてかまいません。

回答No.2

graphaffine

効率はともかく、アルゴリズムを知りたいんだろうけど。
パスの意味が分かってるのかな。
2つ目の例は何故7なんだろう。

お礼

No.3の補足の通りです。

補足

分かりにくくてすいません。

２つ目のグラフについて、次のようにカウントします。

　　１　６　７
　・－・－・－・
　２／　＼５
　・－・－・
　　３　４

よろしくお願いいたします。

回答No.1

Tacosan

うろ覚えだけど, 最長パスは NP困難じゃなかったかなぁ....

お礼

回答ありがとうございます。

探してる途中でNP困難であるという記述はどこかで見ました。
ただ、グラフが小さいのでそれでも現実的な時間でとけるのではないかな、と思っています。