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

解決済

質問者：nanako_04
質問日時：2014/07/23 22:51
回答数：4件

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

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

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

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

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

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

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

ベストアンサー優先
最新から表示
回答順に表示

No.4ベストアンサー

回答者： Tacosan
回答日時：2014/07/25 17:27

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

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

- 0
- 件

通報する

この回答へのお礼

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

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

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

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

通報する

お礼日時：2014/07/26 12:08

No.3

回答者： graphaffine
回答日時：2014/07/25 10:23

#2の補足は一般的に言うパスには成っていません。

あなたのパスの定義は何でしょう。

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

この回答への補足

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

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

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

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

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

==========

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

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

ですので、

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

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

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

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

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