在Neo4j中實現Dijkstra算法

我對Neo4j很新。有人可以向我解釋（請逐步說明）我如何實現Dijkstra算法來找到兩個節點之間的最短路徑？使用Cypher可以簡單地做到嗎？在Neo4j中實現Dijkstra算法

我已經嘗試過的最短路徑算法，但它是非常緩慢：

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , path = (from)-[:CONNECTED_TO*1..5]->(to) 
RETURN path AS shortestPath, 
    reduce(distance = 0, r in relationships(path)| distance+toInt(r.Distance)) 
AS totalDistance 
    ORDER BY totalDistance ASC 
    LIMIT 1

我的節點是：與性能LocationID和LOCATIONNAME 位置我的關係是：CONNECTED_TO財產距離

我有更多的超過6000的關係

請注意在上面的代碼中，我限制爲1..5, 當我沒有定義這個限制時，查詢不會給出任何結果（ke上執行的EPS）

感謝

來源

2014-12-07 Shazu

是有可能用Cypher支架或與Neo4j的REST API的dedicated endpoint。

BTW，從Cypher支架的Neo4j文檔的例子是自我解釋：

http://neo4j.com/docs/milestone/query-match.html#_shortest_path

爲了讓兩個節點之間的最短路徑：

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
path = shortestPath((from)-[:CONNECTED_TO*]->(to)) 
RETURN path

如果你想獲得的所有最短

如果您想按t他降序排列的路徑長度（跳數）：

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to)) 
RETURN paths 
ORDER BY length(paths) DESC

如果你得到最短路徑+的關係距離屬性的總和：

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
path = shortestPath((from)-[:CONNECTED_TO*]->(to)) 
WITH REDUCE(dist = 0, rel in rels(path) | dist + rel.distance) AS distance, p 
RETURN p, distance

來源

2014-12-07 20:36:19

感謝您的迴應克里斯托夫。唯一的附加點（我忘記提及，這是我的錯），是我還希望有最短路徑的總距離作爲查詢的結果。這就是爲什麼我在發佈的查詢中使用了reduce函數。但是，使用此函數往往會使查詢非常緩慢並且實際上不可用，因此您可以提出解決此問題的方法。謝謝 – Shazu 2014-12-07 22:08:08

你可以在return語句中使用它：RETURN path，length（shortestPath）長度爲 – 2014-12-07 22:12:04

感謝您的回覆。節點之間的關係具有屬性「距離」。最短路徑的長度僅僅返回跳數，而不是節點x和節點y（開始和結束節點）之間的實際距離。那麼有可能以有效的方式返回最短路徑的距離嗎？ – Shazu 2014-12-07 22:24:56

在Neo4j中實現Dijkstra算法

回答

相關問題