performance - 2つのノード間のすべてのパスを見つけるための効率的なアルゴリズム

Question

今のところ、無向で重み付けされていないグラフで2つのノード間のすべてのパスを取得する再帰DFSに取り組んでいます。パスを保存しながら、開始ノードと終了ノード、およびノー​​ドとその隣接ノードのDFSを再帰的に取得します。すべてのパスを見つけるためのより効率的な方法があるかどうか疑問に思いましたか？

Answer 1

単純なパスは指数関数的に多く、DFSは基本的にすべてを0で作成しているため、時間はかかりますが、アプローチは正しいです（ただし、これは問題自体の一部であり、アルゴリズムではありません）。

ターゲットに至らないノードが存在する場合は、グラフから除外することで、少し最適化できる可能性があります。失敗した検索を計算する前に効果的にトリミングします。

グラフにサイクルが含まれている場合は、パスの数が無限になる可能性があることに注意してください（ただし、単純なパスの数は有限です）。無限ループを回避し、すべての単純なパスを取得するには、DFSがvisitedセットを維持する必要があることに注意してください。これは、パスごとに変更されます（ノードが「検出」されると、セットに挿入され、スタックからポップされたら、削除されます）。セットから）。

Answer 2

ダイクストラのアルゴリズムを適応させることができます 。2 つの指定されたノード間のすべてのパスを見つけるための再帰アルゴリズムも参照してください。