How to implement Dijkstra's algorithm in Neo4j using Cypher

7
votes

My question is: is it possible to implement Dijkstra's algorithm using Cypher? the explanation on the neo4j website only talks about REST API and it is very difficult to understand for a beginner like me

Please note that I want to find the shortest path with the shortest distance between two nodes, and not the shortest path (involving least number of relationships) between two nodes. I am aware of the shortestPath algorithm that is very easy to implement using Cypher, but it does not serve my purpose.

Kindly guide me on how to proceed if I have a graph database with nodes, and relationships between the nodes having the property 'distance'. All I want is to write a code with the help of which we will be able to find out the shortest distance between two nodes in the database. Or any tips if I need to change my approach and use some other program for this?

2
neo4jcypherdijkstra
there is a recent question related to this one, maybe that helps. – zaboco
yea I asked that question, the answer I received was correct in the sense that I could obtain shortest path (least number of relationships) and the sum of the distances between the nodes....but what I am looking for is the shortest path (least 'distance') so I have to put up another question to clarify that – Shazu
What does "distance" here mean? Do you have some attribute on your relationship that represents the distance over one relationship "hop" between two nodes? – FrobberOfBits
Yes, exactly. Each relationship has a property called distance – Shazu

2 Answers

7
votes

In this case you can implement the allShortestPaths, ordering the paths in an ascending order based on your distance property of the relationships and return only one, based on your last post it would be something like this :

MATCH (from: Location {LocationName:"x"}), (to: Location {LocationName:"y"}) , 
paths = allShortestPaths((from)-[:CONNECTED_TO*]->(to))
WITH REDUCE(dist = 0, rel in rels(paths) | dist + rel.distance) AS distance, paths
RETURN paths, distance
ORDER BY distance
LIMIT 1
1
votes

No, it's not possible in a reasonable way unless you use transactions and basically rewrite the algorhythm. The previous answer is wrong as longer but less expensive paths will not be returned by the allShortestPaths subset. You will be filtering a subset of paths that have been chosen without considering relationship cost.