Dijkstra's algorithm implementation in Neo4j

Question

I am very new to Neo4j. Can someone explain to me (step by step, please) how I could implement Dijkstra's algorithm to find the shortest path between two nodes? Is it possible to just do this with Cypher?

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 

my nodes: Location with LocationID and LocationName properties my relationship: CONNECTED_TO with Distance property

I have over 6,000 relationships

pay attention to the code above, which I limited to 1..5 when I do not define this limit, the query does not give any results (continues to execute)

thanks

Answer 1

Yes, perhaps with Cypher or with a dedicated endpoint API Neo4j ReST.

By the way, examples from the Cypher Neo4j documentation explain themselves:

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

To get 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 transitions) of the tracks 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 want to get shortestPath + the sum of the distance 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 

Answer 2

Another way to execute the request:

install "apoc" in neo4j https://neo4j-contrib.imtqy.com/neo4j-apoc-procedures/#utilities

MATCH (start: node {name: 'First_node_name'}), (end: node {name: 'end_node_name'}) CALL apoc.algo.dijkstra (start, end, 'weight_property', 1.0) YIELD path, weight return path, weight

---

PS 'weight_property' is a PropertyName that should have your relationship (weight_property = 225454)

returned two values:

1. the path is the path that was found;
2. weight is the total weight number that was calculated for each relationship