Implementing Dijkstra's algorithm in Neo4j

6
votes

I am very new to Neo4j. Could someone kindly explain to me (step-by-step please) how I could implement the Dijkstra's algorithm to find the shortest path between two nodes? Is it possible to simply do it using 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 are: Location with properties LocationID and LocationName my relationships are: CONNECTED_TO with property Distance

I have more than 6000 relationships

please note in the code above that I have limited to 1..5 when I do not define this limit, the query does not give any results (keeps on executing)

thanks

2
neo4jcypher

2 Answers

14
votes

Yes it is possible with Cypher or with a dedicated endpoint of the Neo4j ReST API.

BTW, the examples from the Cypher Neo4j documentation are self explaining :

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

To get the 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 hops) of the paths 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 to to get the shortestPath + the sum of the relationship 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
1
votes

Another way to perform the query:

install "APOC" in neo4j https://neo4j-contrib.github.io/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

P.S. 'weight_property' this is PropertyName which must have your relationship (weight_property=225454)

returned two values:

  1. path - this is the path that was found;
  2. weight - summary number of weight that was colculated from each relationship