"Bidirectional Dijkstra" by NetworkX

Question

双方向検索（this）を使用して、最短パスのDijkstraのアルゴリズムのNetworkX実装を読みました。この方法の終了点は何ですか？

Answer 1

私はnetworkxの実装でこれをベースにします。

双方向ダイクストラは、両方向で同じノードに遭遇すると停止しますが、その時点で返されるパスはそのノードを経由しない可能性があります。それは、最短経路の最良の候補を追跡するために追加の計算を行っています。

私は

（this answerに）あなたのコメントに私の説明を基にするつもりだが、この単純なグラフ（ノードA、B、C、Dと、E）を考えます。 A-> B：1、A-> C：6、A-> D：4、A-> E：10、D-> C：3 "、" C-> E：1 "となる。私はDijkstraアルゴリズムを両側で使っています：前方ではAとDの後にBを見つけ、Eの後にCを見つけてDを見つけました。この時点で両方のセットは同じ頂点と交差点を持っています。これは終了点ですか、それとも続行する必要がありますか？この答え（A→D→C→E）が正しくないためです。私は反例で（無向）ネットワーク上のnetworkxの双方向のダイクストラを実行すると

は、あなたがコメントすることを主張："A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1"：

は参考のため、ここではグラフだそれは私を与える：(7, ['A', 'C', 'E'])、ないA-D-C-E。

の前に、問題が誤解されています。の前に停止しています。ノードを見つけるという点ではまさに期待していることですが、最短経路を見つけるために追加の処理が行われています。両方の方向からDに達するまでには、もう少し短い「候補」パスがすでに収集されています。ノードDが両方の方向から到達し、最短経路の一部に終わるという保証はありません。むしろ、ノードが双方向から到達した時点で、現在の候補最短経路は、それが継続している場合に見つかる候補経路よりも短い。

アルゴリズムは、2つの空きクラスタ、AまたはE

{}   {} 

に関連する各で始まり、それがそれぞれの周囲に「クラスター」を構築します。それは最初Aは（現在は空である）E周りクラスタに既にある場合今ではチェックA

{A:0}   {} 

に関連付けられているクラスタにAを置きます。そうではない。次に、各隣人をAのところで調べ、それらがクラスタ内にあるかどうか確認します。E。ではない。次に、隣接するすべてのノードを、Aの次の隣人のヒープ（順序付きリストのような）に配置します。 A

clusters     .....  fringes 

{A:0}   {}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[] 

の 'フリンジ' は今ではEをチェックし、これを呼び出します。 Eについては対称的なことをします。 Eをクラスタに配置します。 Eがクラスタ内のAにないことを確認します。その後、隣接するすべてのノードをチェックして、クラスタ内にあるものがAの周辺にあるかどうかを確認します（存在しない）。次に、フリンジをEにします。

clusters         fringes 
{A:0}   {E:0}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

今度はAに戻ります。リストからBが取り出され、Aの周りにクラスタに追加されます。 Bのネイバーが、Eのクラスター内にあるかどうかをチェックします（考慮するネイバーはありません）。だから我々は持っている：

clusters         fringes 
{A:0, B:1}  {E:0}  .....  A:[(D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

戻るEへ：私たちはEのC TOT彼クラスタを追加し、Cのいずれかの隣人がAのクラスタ内にあるかどうかを確認してください。何を知っていますか、Aがあります。そこで我々はの候補を最短経路A-C-E、距離7で持っています。フリンジにEを追加するには、Dを追加します（距離は4です.1 + 3なので）。我々は持っている：

clusters         fringes 
{A:0, B:1}  {E:0, C:1}  ..... A:[(D,4), (C,6), (E,10)] 
             E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

戻るAへ：私たちは、そのフリンジ、Dから次の事を得ます。クラスタにAについて追加し、その隣のCがクラスタ内に約Eであることに注意してください。したがって、新しい候補パスA-D-C-Eがありますが、長さが7より大きいため、破棄します。

clusters         fringes 
{A:0, B:1, D:4}  {E:0, C:1}  ..... A:[(C,6), (E,10)] 
              E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

ここではEに戻ります。我々はDを見ます。それはクラスタAの周りにあります。私たちが直面する今後の候補経路は、少なくとも私たちが今までに辿った道（）と同じくらいの長さになると確信できます（この主張は必ずしも明白ではありませんが、このアプローチの鍵です）。だから私たちは止めることができます。先に見つかった候補パスを返します。