我已收到製作social graph的任務，其中，center中的一個用戶顯示他擁有的連接。詢問社交網絡分析（SNA）算法
但是在我們達成目標之前，我們的重點是我們如何確定2個用戶之間的shortest path。
我發現了一些算法，但它似乎花了很多時間，而且由於它是關於社交鏈接的，我們正在尋找一種速度最快的算法，因爲我們需要定期運行它跟上朋友的更新。
那麼，你知道哪個是確定兩個用戶之間最短路徑的最快方法嗎？ PS：如果你知道一個PHP & MySQL的例子，我會給你一個虛擬啤酒（或可樂）。 ：D
Dijkstra's Algorithm找到圖上兩個節點之間的最短路徑。
在我看來，如果您要繪製整個圖表，最簡單的方法是跟蹤每個人的路徑，因爲他們被添加到圖表中。所以對於朋友來說，路徑就是「主人 - >朋友」。然後，當你添加他們的每個朋友到圖中，存儲路徑「主要人物 - >朋友1 - >朋友2」等。
如果我腦海中的圖片是準確的，那看起來像是最簡單的方法這樣做，但我可能會有點誤解。
你想要的是一個all-pairs shortest path算法;如果必須爲圖形全局生成對，則比爲每對運行最短路徑算法要快。保持這種更新是另一個問題 - 請注意，每次添加圖形連接時都必須執行此操作，而不是每次添加人員時執行此操作。如果這是一個生產站點，可能值得將圖形生成保持爲比使用PHP語言編寫語言更快的離線任務，並將結果寫回db。你可能會發現現有的C++實現。
Dijsktra的算法在加權圖上運行良好。在社交圖中，所有邊都具有相同的權重。所以Dijkstra的算法變成了BFS。然而，在密集的圖表上，每個級別檢查的節點列表將是巨大的。你可以做的一個優化是，從兩端開始搜索（A和B）。