How to implement Dijkstra's algorithm in Neo4j using Cypher

Question

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?

Answer 1

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

Answer 2

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.