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 the REST API, and it is very difficult to understand for a beginner like me.

Note that I want to find the shortest path with the smallest distance between two nodes, and not the shortest path (with the least number of relations) between two nodes. I know about the shortestPath algorithm, which is very easy to implement using Cypher, but it does not serve my purpose.

Please advise me how to proceed if I have a graph database with nodes and relationships between nodes that have the distance property. All I want to do is write code with which we can 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 allShortestPaths, sorting the paths in ascending order based on the distance property of the relations and returning only one, based on your last message, it will look 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, this is not reasonably possible if you are not using transactions and basically rewrite the algorithm. The previous answer is incorrect, since a longer but less expensive path will not be returned by a subset of allShortestPaths. You will filter a subset of the paths that were selected without regard to the value of the relationship.