在 Neo4j 中实现 Dijkstra 算法 [英] Implementing Dijkstra's algorithm in Neo4j
问题描述
我对 Neo4j 很陌生.有人可以向我解释(请逐步说明)我如何实现 Dijkstra 算法来找到两个节点之间的最短路径?是否可以简单地使用 Cypher 来完成?
I am very new to Neo4j. Could someone kindly explain to me (step-by-step please) how I could implement the Dijkstra's algorithm to find the shortest path between two nodes? Is it possible to simply do it using Cypher?
我已经尝试过shortestPath算法,但是速度很慢:
I already tried the shortestPath algorithm, but it is very slow:
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 与财产距离
my nodes are: Location with properties LocationID and LocationName my relationships are: CONNECTED_TO with property Distance
我有超过 6000 个关系
I have more than 6000 relationships
请注意在上面的代码中我限制为 1..5当我没有定义这个限制时,查询不会给出任何结果(继续执行)
please note in the code above that I have limited to 1..5 when I do not define this limit, the query does not give any results (keeps on executing)
谢谢
推荐答案
是的,可以使用 Cypher 或 Neo4j ReST API 的专用端点.
Yes it is possible with Cypher or with a dedicated endpoint of the Neo4j ReST API.
顺便说一句,来自 Cypher Neo4j 文档的示例是自我解释的:
BTW, the examples from the Cypher Neo4j documentation are self explaining :
http://neo4j.com/docs/milestone/query-match.html#_shortest_path一个>
获取两个节点之间的最短路径:
To get the shortestPath between two nodes :
MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) ,
path = shortestPath((from)-[:CONNECTED_TO*]->(to))
RETURN path
如果你想得到所有最短的
If you want to get all the shortest
MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) ,
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to))
RETURN paths
如果要按路径的长度(跳数)降序排序:
If you want to order by the length (number of hops) of the paths in descending order :
MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) ,
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to))
RETURN paths
ORDER BY length(paths) DESC
如果要得到最短路径+关系距离属性的总和:
If you to to get the shortestPath + the sum of the relationship distance property :
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
这篇关于在 Neo4j 中实现 Dijkstra 算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!