algorithm - <= x である最長パスの検索 (加重無向グラフ)

Question

いくつかの x 変数以下の最長パスを見つけるアルゴリズムは考えられません。ダイクストラのアルゴリズムを使用すると、最長パスを簡単に取得できますが、問題で使用できるかどうかはわかりません。

Answer 1

ダイクストラのアルゴリズムは、最長経路ではなく最短経路を提供します。

最長の（単純な）パスを見つけるのはNP困難です。問題は最長パス問題に縮退する可能性があるため（xをすべてのエッジの重みの合計に等しくします。これは最長パスの長さの上限です）、これもNP困難です。

ツリー検索を使用することはできますが、扱いにくい可能性があります。

単純でないパス（ノードは複数回トラバースされる可能性がある）を検討している場合、それは別の問題です。退化したケースはナップサック問題であり、これもNP困難です。

Answer 2

最長パスを見つけるために DFS アルゴリズムを使用できます。検索すると、Depth First Search & Directed Acyclic Graphsなどの便利な記事が見つかります。