Bi Directional Dijkstra

双方向のダイクストラ

問題

非陰性エッジの重み、ソース頂点とターゲット頂点のグラフが与えられました。 SとTの間の最短パスを見つけます

しかし、なぜDijkstraのアルゴリズムを使用して問題を解決しないのですか？

0（e + vlogv）は、Dijkstraのアルゴリズムの最悪の時間の複雑さであり、非常に高速です。ただし、2億億枚の頂点と5,000万件のエッジを備えたグラフの場合、平均で数秒間機能します。そのため、大幅に高速なものが必要です。

双方向の検索の詳細に入る前に、 「6つの分離度」の概念を調査しましょう。

• 1929年、ハンガリーの著者であるフリギース・カリンシーが、彼の短編小説チェーンで「6度の分離」の概念を初めて提案しました。
• 6度の分離は、世界のすべての生物や他のすべてが互いに6段階以下であるという考えです。

さて、最も人気のあるソーシャルネットワークであるFacebookを見てみましょう。 Facebookの平均的な人に約100人の友人がいるとします。その後、その人の友人の友人を考慮すると、友人の10,000人の友人である100*100になります。 「友達の友達の友人」を考慮すると、それは100倍または100万人になります。そして、私たちがその6倍を続けるならば、私たちは1兆人を産むでしょう。

しかし、世界人口は76億人です。

さて、ソーシャルネットワーク上の接続を介して、2人のランダムな人AとBの間の最短パスをどのように見つけますか？

双方向の検索を検討しましょう。したがって、私たちは友人の友人の友人の友人とBの友人の友人の友人の友人を検討します。

AとBの両方で友人の友人の約100万人の友人がいることに注意してください。したがって、この場合、合計で200万人しか検討しません。

通常のDijkstraのアルゴリズムは、AとBの間で最短のパスを見つけるために、ソーシャルネットワーク上で約200億人の人々を見る必要があります。

双方向の検索とは何ですか

これでは、2つの同時検索を実行します。1つは初期状態から、もう1つはゴールから後方になり、2つが中央で出会ったときに停止します。

グラフg上の双方向のダイクストラの擬似コード

• GRをビルドする（逆グラフ）
• Gのs（source）およびgrのt（ターゲット）からdijkstraを開始します
• GとGrのDijkstraステップの代替
• 頂点「V」がgとgrの両方で処理されている場合は停止します。
• SとTの間の最短パスを計算します。

sとtの間の最短経路の計算： dist [u]をgのsからのフォワードダイクストラの距離推定値とします。いくつかのノード「V」がgとgrの両方で処理された後、sからtまでのいくつかの最短パスは、g、g、 d（s、t）= dist [u] + dist [u]のいずれかで処理されるいくつかのノード「u」を通過します。