Neo4j - Finding the Shortest Path between two nodes based on relationship property

Question

I'm trying to figure out if there's someway to get the shortest distance between two nodes based in a relationship sum, given this example: neo4j image example

Code for image above:

CREATE (some_point_1:Point {title:'Some Point 1'})
CREATE (some_point_2:Point {title:'Some Point 2'})
CREATE (some_point_3:Point {title:'Some Point 3'})
CREATE (some_point_4:Point {title:'Some Point 4'})
CREATE (some_point_5:Point {title:'Some Point 5'})
CREATE (some_point_6:Point {title:'Some Point 6'})

CREATE (some_point_1)-[:distance {value:100}]->(some_point_2)
CREATE (some_point_2)-[:distance {value:150}]->(some_point_4)
CREATE (some_point_1)-[:distance {value:200}]->(some_point_3)
CREATE (some_point_3)-[:distance {value:300}]->(some_point_4)
CREATE (some_point_2)-[:distance {value:500}]->(some_point_5)
CREATE (some_point_4)-[:distance {value:300}]->(some_point_5)
CREATE (some_point_5)-[:distance {value:300}]->(some_point_6)
CREATE (some_point_6)-[:distance {value:300}]->(some_point_1)

In this example the shortest path should be: some_point_1 > some_point_2 > some_point_4 > some_point_5 (100+150+300 = 550)

Is something like this possible with Cypher?

Answer 1

The shortestPath function in Cypher does not take into account accumulating of relationship properties, so this:

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
MATCH p=shortestPath((start)-[:distance*]->(end))
RETURN p

would find the shortest path from start to end based on the number of relationships in the path.

You could reduce on the sums of the distances:

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
MATCH p=(start)-[:distance*]->(end)
WITH p,reduce(s = 0, r IN rels(p) | s + r.value) AS dist
RETURN p, dist ORDER BY dist DESC

But the problem here is that you need to calculate the total distance for all paths from start to end. To be more efficient you want to use a graph search algorithm like Dijkstra's algorithm or A*, both of which are implemented in Neo4j's Java API.

In Neo4j 3.0 these algorithms are exposed in Cypher through the APOC procedure library. Once you install APOC you can call the procedure from Cypher:

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
CALL apoc.algo.dijkstra(start, end, 'distance', 'value') YIELD path, weight
RETURN path, weight

Answer 2

Cypher has a shortestPath() function, that combined with predicates and a some trial and error will probably do what you want.

But to save time, it's easier to use neo4j APOC Procedures, which includes a weighted dijkstra shortest path algorithm that should be a perfect fit for what you want.

I haven't used it yet, but I think the syntax (after matching on startNode and endNode, using the name of your relationship and the property used for weight) is something like

CALL apoc.algo.dijkstra(startNode, endNode, 'distance', 'value') 
YIELD path, weight

As for taking direction into account, the wiki documentation doesn't say it outright, but it looks like < or > is added to the appropriate end of the relationship label, I think, so 'distance>' is probably the more correct parameter, if you want it to respect direction.