在Neo4j中实现Dijkstra算法

Question

我是Neo4j的新手.有人可以向我解释(请一步一步)我如何实现Dijkstra的算法来找到两个节点之间的最短路径？是否可以使用Cypher简单地完成它？

我已经尝试过shortestPath算法,但速度非常慢:

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属性Distance

我有6000多个关系

请注意在上面的代码中我限制为1..5,当我没有定义此限制时,查询不会给出任何结果(继续执行)

谢谢

Answer 1

是的,可以使用Cypher或Neo4j ReST API 的专用端点.

顺便说一下,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

如果你想得到所有最短的

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

如果要按降序排列路径的长度(跳数):

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

如果要获取shortestPath +关系距离属性的总和:

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