Javaでのダイクストラ（またはその他の送信元から宛先への最短経路アルゴリズム）の双方向検索（別名「中間一致」アルゴリズム）の実装を探しています。
双方向検索処理は見た目よりも難しいので（グラフアルゴリズム、p.26）、車輪の再発明を行う前に既存の実装を検討したいと思います。
PS：私は双方向検索について話しているのですが、双方向グラフと混同しないでください）
トリッキーなグラフの例を次に示します。
質問する
9883 次
1 に答える
7
はい、少なくともJavaにはあります：https ：//github.com/coderodde/GraphSearchPal/blob/master/src/main/java/net/coderodde/gsp/model/support/Bi directionDijkstraPathFinder.java
双方向ダイクストラのアルゴリズムでは、実際には2つの「ダイクストラのアルゴリズム」を維持します。前方検索と後方検索です。現在、前方検索は一方向ダイクストラのアルゴリズムによく似ています。ただし、後方検索は「逆」の方法で進行します。有向エッジ（口語的にアークと呼ばれる）がある場合、前方検索はそれをからに(u, v)トラバースしますが、後方検索は反対方向に同じことを行います。uv
2つの検索プロセスは（通常）ソースノードとターゲットノードの間のどこかで満たされるため、別の終了条件が必要です。これは、双方向ダイクストラのアルゴリズムでは次のようになります。
g(top(OPEN_forward)) + g(top(OPEN_backward)) > l
ここlで、はソースノードとターゲットノード間のこれまでに知られている最短のパスの長さです。
双方向バージョンでのみ表示される可能性のある追加のコードは、ノードの値を改善するたびに最短パス候補を短縮する可能性をチェックしています。g（ノードのg値はu、検索が開始されたノードからの最短（これまでに知られている）距離uです。）
于 2016-03-21T13:14:19.247 に答える