Реализация алгоритма Дейкстры в Neo4j

Question

Я очень новичок в Neo4j. Может ли кто-нибудь любезно объяснить мне (шаг за шагом, пожалуйста), как я мог бы реализовать алгоритм Дейкстры, чтобы найти кратчайший путь между двумя узлами? Можно ли просто сделать это с помощью 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 со свойством Расстояние

У меня есть еще чем 6000 отношений

Обратите внимание, что в приведенном выше коде я ограничился 1..5 , когда я не определяю этот предел, запрос не дает никаких результатов (ke EPS на выполнение)

благодарит

Answer 1

Да, это возможно с Cypher или с dedicated endpoint по API Neo4j Rest.

Кстати, примеры из документации Cypher Neo4j являются самостоятельным объяснение:

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

Чтобы получить shortestPath между двумя узлами:

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 

Если вы хотите сделать заказ по t он длина (количество прыжков) из путей в порядке убывания:

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