在社交網路中，如何去計算中兩個人之間的最短路徑？

1樓：紅色番茄醬

networkx可以實現

import

networkx

asnxG=

nx.Graph

()#建立關係圖

data=[(

1,2),(2,

3),(1,

4),(3,

4)]G.

add_edges_from

(data

)#新增三條邊（包括4個節點）p=

nx.shortest_path(G

,source=1

,target=4

)#求最短路徑，從節點1出發，到節點4

('1到4最短路徑為：',p

)#輸出結果

輸出為：

1到4最短路徑： [1, 4]

2樓：蛛撕碼記

用 Neo4j1.建立節點

create

(p3:User ),

(p4:User ),

(p5:User ),

(p6:User ),

(p7:User ),

(p8:User ),

(p9:User ),

(p10:User );

2.建立關係

match (p3),(p4)

where p3.name="張三" and p4.name="李四"

create (p3)-[:HAS_FRIEND]->(p4);

match (p3),(p5)

where p3.name="張三" and p5.name="王五"

create (p3)-[:HAS_FRIEND]->(p5);

match (p4),(p6)

where p4.name="李四" and p6.name="趙六"

create (p4)-[:HAS_FRIEND]->(p6);

match (p4),(p7)

where p4.name="李四" and p7.name="錢七"

create (p4)-[:HAS_FRIEND]->(p7);

match (p5),(p8)

where p5.name="王五" and p8.name="孫八"

create (p5)-[:HAS_FRIEND]->(p8);

match (p5),(p9)

where p5.name="王五" and p9.name="楊九"

create (p5)-[:HAS_FRIEND]->(p9);

match (p6),(p10)

where p6.name="趙六" and p10.name="吳十"

create (p6)-[:HAS_FRIEND]->(p10);

3.查詢兩人（張三和吳十）之間最短路徑

match p = shortestPath( (p3:User )-[:HAS_FRIEND*..3]->(p10:User ) ) return p;

結果如下圖：

3樓：

MapReduce不太擅長這種型別的問題。

大概掃了一遍，發現沒人提到pregel。我這個人覺得pregel在這方面還是很有優勢的，畢竟它的思想就是「think like vertex」，生成了圖之後你想怎麼玩就怎麼玩，不過能不能在O(lg n)次迭代內完成還要看你問題和演算法。不過如果真的如題主說的，迭代六次就搞定了

4樓：朱涵俊

乙個陌生人通過哪幾個人認識難道不是2層關係而已嗎，就是這個陌生人認識我朋友中的哪幾個而已，有這麼複雜嗎？

6度關係無解，解出來也沒意義。就按每個人100個好友計算，6度關係就要計算1萬億人了，地球總共才多少人。

5樓：

不就是跟路由選擇最近節點的原理一樣嗎…

假設從北京a到鄭州z有好多節點

路由如何選擇最短路徑，

同理，找兩個人的中間的最短路徑和找兩個城市（mac位址）間的最短路徑不是乙個道理嗎？

6樓：時冰藍

BFS可解，當然你可以限制乙個最大RAM消耗，超過此值認為無解，或者你用分布式等手段突破RAM制約，不過那已經和演算法本身沒關係了。

也可以用點啟發式方法，兩側BFS然後選取順序依照相關性之類的。這個就看要求到什麼程度了。

7樓：熊徽

我在neo4j中儲存了乙個圖，節點大約2500-4000個，怎麼計算兩兩之間的路徑，並且對計算出來的路徑掃瞄一遍就可以了，怎麼實現較高效一點，採用neo4j中的Dijkstra演算法 or A*演算法？貌似不能一次得到乙個點到其他所有節點的路徑，這樣的話麻煩就來了。

8樓：白伯純

我們是從兩端的使用者向中間遍歷的，每一級都是廣度優先遍歷。

算出的路徑不一定是最短路徑，同時最短路徑也不一定是最優路徑。

我個人在這個應用上的使用需求，是熟人優先。所以如果要產品化，我會設計讓使用者介入選擇。

9樓：李垚

我有一種想法（當然肯定不是朋友網的做法），把每個使用者的終端當作計算機網路模型中的乙個路由器，然後通過類似網路層選路協議的方式進行計算，這樣似乎理論上可以分布式地計算出所有人之間的最短路徑，不過需要他們都有一定的登入時間，並在每台機器上儲存大量其他使用者的資料。

10樓：資料控

感謝朋友網這個驚豔的功能。以下僅為個人猜測，估計都是錯的，拋磚引玉獻醜了

假設朋友網的每乙個人都能獲得300個直接人脈，那麼要計算甲到乙的路徑，需要遍歷甲的六度人脈300^6的確很可怕。。

不過實際上，查詢甲和乙2個人的關係，那麼只要計算甲的三度內人脈300^3=2700w人，和乙的三度內人脈2700w人是否有相同的就可以了，這個數量級會比較小一點。實際上個人查詢過，和某個人沒法建立聯絡，說明朋友網實際上應該是控制了N度關係，計算量太大的7度關係八度空間之類的應該是不考慮了。

實際操作中，還可以根據地區，職業，年齡，學校，等因素進行預判縮小範圍。

在社交網路中，如何去計算中兩個人之間的最短路徑？

在感情中，兩個人怎樣才能順利磨合？

愛情中兩個人怎麼相處才能長久

兩個人的交往中應該講理性嗎？

其他用戶還看了：