私はsocial graphという仕事を受け取りました。ここでは、centerの1人のユーザーが自分の接続を示しています。ソーシャルネットワーク分析（SNA）アルゴリズムの依頼
しかし、これまでに2人のユーザーの間でshortest pathをどのように判断できるかについて説明しました。
私はアルゴリズムをいくつか見つけましたが、時間がかかるようで、ソーシャルリンクのため、定期的に実行する必要があるため最速のものを探しています友人の最新情報に追いつく。
だから、2人のユーザーの間の最短経路を判断する最も速い方法はどれでしょうか？
PS：PHP &の例を知っていれば、私はあなたにバーチャルビール（またはコークス）を提供します。 ：D
Dijkstra's Algorithmグラフ上の2つのノード間の最短経路を検出します。
とにかくグラフ全体を描くのであれば、グラフにグラフが追加されるので、各人のパスを追跡するのが最も簡単です。だから、人の友人のために、その道はちょうど "主人 - >友人"です。次に、各友達をグラフに追加すると、「本人→友人1→友人2」などのパスを保存します。
私の心の中の画像が正確ならば、これは最も簡単な方法ですそれをしてください、しかし、私は多少誤解しているかもしれません。
アルゴリズムはall-pairs shortest pathです。グラフのペアをグローバルに生成する必要がある場合は、すべてのペアに対して最短パスアルゴリズムを実行するよりも迅速です。これを更新したままにすることは別の問題です。人を追加するときだけでなく、グラフに接続を追加するたびに行う必要があります。これがプロダクションサイトの場合は、phpよりも速い言語で書かれたオフラインタスクとしてグラフの生成を維持し、その結果をdbに書き戻す価値があります。おそらく既存のC++実装がそこにあることに気付くでしょう。
Dijsktraのアルゴリズムは、加重グラフでうまく機能します。ソーシャルグラフでは、すべてのエッジのウェイトが同じです。だからダイクストラのアルゴリズムはBFSになります。しかし、密度の高いグラフでは、各レベルで調べられたノードのリストが膨大になります。最適化の1つは、両端（AとB）から検索を開始することです。