ダイクストラのアルゴリズムを使用して、理想的なパスを解決しています。プログラムの一部として、アルゴリズムは数千回呼び出されます。
半分以上の確率でパスは不可能であり、ダイクストラはこれを理解するのに非常に長い時間がかかります (小規模なテストでは、可能なパスは合計 2 秒で解決されましたが、不可能なパスは合計 25 秒かかりました)。
その結果、アルゴリズムで時間を無駄にする前に、2 つのノード間のパスを見つけることさえ可能かどうかを非常に効率的に確認できる方法があるかどうかを知りたいです。これを行うための非常に効率的な方法はありますか？
ありがとう、ダン
制約なし、使い捨て
制約のないグラフで、プログラムがこれまでに (またはその一部でさえ) 見たことがなく、二度と見られない。あなたができる唯一のことは、幅優先検索または深さ優先検索です。
メモリが問題になる場合は、インクリメンタルな深さ優先検索の使用を検討してください。
グラフで複数のスレッドを起動して、さまざまなブランチを確認することを検討してください。すべてが安全に検査および書き込みできる同時共有データ構造を持つことにより、作業を繰り返さないように調整する必要があります。並行性を使用すると、一部のスレッドを最初から最後まで検索し、他のスレッドを最後から最初まで検索することができます。
サイクルのあるグラフでは、無限ループを実行しないように、ノードを訪問済みとしてマークする必要があります。
制約、使い捨て
グラフと目的について考えてください。
グラフは密か疎か?
負のエッジの重みはありますか? 負のサムサイクル？
台形則に従っていますか？
パスがあっても気にしない最大距離はありますか?
グラフは非循環的ですか?
グラフは「単純」ですか？
いくつかの作業により、グラフの dfs よりも優れたアプローチを見つけることができる場合があります。また、dfs を高速化する別の方法でグラフを構成できる場合もあります。場合によっては、検索中にそれほど多くのデータを保存する必要がないことが利点になる場合があります。
制約、多用途
それだけの価値がある場合は、Floyd-Warshall を実行して、ノードのすべてのペア間の最短経路を解決することもできます。アルゴリズムには時間がかかりますが、クリティカル セクションで最短パスのルックアップを実行できる場合は有利です。
最短パスを事前に解決するのではなく、グラフで最初の dfs を実行することにより、接続されたコンポーネントを事前に解決できます。
グラフが変化する可能性がありますが、大幅ではない場合は、毎回最初からやり直すのではなく、事前に計算された結果を単純に変更できる場合があります。
最後の思い
グラフのサイズと複雑さは重要な考慮事項です。小さくて密に接続されたグラフに最適なアルゴリズムは、大きなまばらなグラフまたはツリーでは異なります。
同じグラフで複数のパス ルックアップを実行していますか? その場合、グラフから離れた一連の連続したスペースを維持する必要があります。これは、次の方法でライブで実行できます。
（2）の正確な最良のメカニズムは、グラフの性質に密接に依存しているため、別の質問に任せます.