圖中任意兩個節點之間的最長最短路徑

我試圖找到兩個在我的Neo4j數據庫中彼此距離最遠的節點。爲了我的分析目的，我正在考慮兩個節點之間的最短距離作爲它們之間的距離。因此，最遠的兩個節點將具有它們之間最長的最短路徑。我使用Cypher的以下語法來查找最短的節點。圖中任意兩個節點之間的最長最短路徑

給定兩個節點，如Neo4j示例文檔http://docs.neo4j.org/chunked/milestone/query-match.html#match-shortest-path中所示，我可以運行以下Cypher查詢。

MATCH p = shortestPath((martin:Person)-[*..15]-(oliver:Person)) 
WHERE martin.name = 'Martin Sheen' AND oliver.name = 'Oliver Stone' 
RETURN p

我的數據庫有超過1億個節點。蠻力的方式顯然需要很長時間。有沒有簡單或更快的方法來獲得這兩個節點？

[作爲一個額外的皺紋..圖進行加權，但這個細節可以忽略不計。]

來源

2013-10-19 Anshul

你正在尋找一個單一來源的最短路徑列表，然後試圖確定哪些是最長的？ – Nicholas

是的。我的目標是找到兩個相距甚遠的節點，任何節點。放在上下文中，我仍然在努力尋找派系，正如你在前面的帖子中所建議的那樣。我正在試驗分區圖。爲了有效地分割它們，我需要兩個相距很遠的節點，以儘量減少它們屬於同一個子圖的機會。 PS - 我沒有正式的圖表教育，所以我正在嘗試創建一些不完美的「make do」解決方案，但要完成工作。感謝您回覆。 – Anshul

嗨@Anshul，只是想問問你是如何解決問題的？ – lmazgon

如果我正確地讀這篇文章，你想all-pairs shortest path。這會給你一個列表，每個節點都是一個源，並且是到其他每個節點的最短路徑。雖然它確實按重量計算，但您可以簡單地將1的重量用於一切。

你必須自己用Java來實現，因爲Cypher沒有這方面的東西。

來源

2013-10-19 19:51:24 Nicholas

是的，最好的方法是使用服務器擴展來實現或重用Java API和算法，請參閱http://docs.neo4j.org/chunked/milestone/server-plugins.html –

圖中任意兩個節點之間的最長最短路徑

回答

相關問題