非巡回グラフで、長さ L のパスが 2 つのノード間に存在するかどうかを調べようとしています。私の質問は、この場合に使用するのに最適で最も単純なアルゴリズムは何かということです。
グラフには最大 50 個のノードと 100 個のエッジがあることに注意してください。
DFS を使用してすべてのパスを検索し、そのパスが 2 つのノード間に存在するかどうかを確認しようとしましたが、オンライン ジャッジから「Time Limit Exceeded」という回答が得られました。
均一コスト検索アルゴリズムも使用しましたが、否定的な応答もありました。
このような問題を解決するためのより効率的な方法が必要です。ありがとうございました。
DFSアプローチよりも高速になるかどうかはわかりませんが、実行可能な解決策が得られます：
グラフを行列として表現し、次の場合にのみ i と j の間に長さ L のパスが存在することAを計算します。A^LA[i][j] != 0
また、DFS ソリューションに関して: DFS内のすべてのパスを見つける必要はありません。長さが必要な長さを超えたら、長さ <= L のパスに制限し、このトリムによっていくつかの検索を行う必要があります。長さ L のパスがターゲットに到達したら、検索を回避することもできます。
もう 1 つの可能な最適化は、双方向検索です。
グラフは非循環であるため、頂点をトポロジー的に並べ替えることができます。開始頂点 A と終了頂点 B に名前を付けましょう。
ここで、コア アルゴリズムが開始されます。各頂点について、A からこの頂点までのすべての可能な距離をカウントします。最初は、A から A への長さがゼロの 1 つのパスがあります。次に、トポロジー順に頂点を取得します。頂点 x を選択する場合: 各前任者を見て、ここで可能な距離を更新します。
これは O(N^3) 時間で実行されます。
すべての頂点について原点までの最小距離を保存する代わりに、必要な距離以下のすべての可能な距離を保存する、変更されたダイクストラ アルゴリズムを使用できます。
次のアルゴリズムを使用して、ツリー内の最長パスを見つけることができると思います。これは、グラフが接続されていることを前提としています。接続されていない場合は、接続されている各コンポーネントでこれを再実行する必要があります。
明らかに、このパスが L よりも長い場合は、それを短くして長さ L のパスを見つけることができます。