ソーシャル グラフを作成するタスクを受け取りました。ここでは、1 人のユーザーを中心に、そのユーザーのつながりを示しています。
しかし、そこに到達する前に、2 人のユーザー間の最短経路を決定する方法に焦点を当てます。
それを行うためのアルゴリズムをいくつか見つけましたが、時間がかかりそうです.ソーシャルリンクに関するものであるため、追いつくために定期的に実行する必要があるため、最速のものを探しています.友達の更新。
では、2 人のユーザー間の最短経路を決定する最速の方法はどれか知っていますか?
PS: PHP と MySQL の例を知っていれば、仮想のビール (またはコーラ) を差し上げます。:D
ダイクストラのアルゴリズムは、グラフ上の 2 つのノード間の最短経路を見つけます。
必要なのは、すべてのペアの最短パスアルゴリズムです。グラフのペアをグローバルに生成する必要がある場合は、すべてのペアに対して最短パス アルゴリズムを実行するよりも高速です。これを更新し続けることは別の問題です。人を追加するたびだけでなく、接続をグラフに追加するたびに更新する必要があることに注意してください。これが本番サイト用である場合、php よりも高速な言語で記述されたオフライン タスクとしてグラフ生成を維持し、その結果をデータベースに書き戻す価値があるかもしれません。おそらく、既存の C++ 実装が見つかるでしょう。
Dijsktra のアルゴリズムは、加重グラフでうまく機能します。ソーシャル グラフでは、すべてのエッジの重みが同じです。したがって、ダイクストラのアルゴリズムは BFS になります。ただし、密なグラフでは、各レベルで検査されるノードのリストが膨大になります。できる最適化の 1 つは、両端 (A と B) から検索を開始することです。
とにかくグラフ全体を描画する場合、グラフに追加された各人のパスを追跡するのが最も簡単だと思います。その人の友達の場合、パスは単に「メインの人 -> 友達」です。次に、それぞれの友人をグラフに追加しながら、「主要人物 -> 友人 1 -> 友人 2」などのパスを保存します。
頭の中にあるイメージが正しければ、それが一番簡単な方法のように思えますが、少し誤解されているかもしれません。