在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多个亲戚

请注意上面的代码中我限制为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或

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

如果你想得到最短的

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屋！