How to search the shortest distance between a set of nodes using Cypher

Question

I'm trying to figure out if there's someway using cypher in Neo4j to get the shortest distance between a group of nodes.

Some notes to take account for this search:
- Distance is a property of the relationships between nodes. Distance values are in meters
- All nodes have a relationship between them with a given distance.
- The start and end nodes to follow must be the same node.

This is what kind of input i want:

MATCH
(root) -[root_p1:PATH_TO]-> (p1), (root) -[root_p2:PATH_TO]-> (p2), (root) -[root_p3:PATH_TO]-> (p3), (p1) -[p1_root:PATH_TO]-> (root), (p1) -[p1_p2:PATH_TO]-> (p2), (p1) -[p1_p3:PATH_TO]-> (p3), (p2) -[p2_root:PATH_TO]-> (root), (p2) -[p2_p1:PATH_TO]-> (p1), (p2) -[p2_p3:PATH_TO]-> (p3), (p3) -[p3_root:PATH_TO]-> (root), (p3) -[p3_p1:PATH_TO]-> (p1), (p3) -[p3_p2:PATH_TO]-> (p2)
WHERE ID(root) = 10 AND ID(p1) = 1 AND ID(p2) = 2 AND ID(p3) = 3
.
.
.

And then the result should be correct sequence of nodes that contribute to get the shortest path possible.

It is not clear what should be on output. It would be better if you bring an example of input data and the desired result. — stdob--

cybersam cybersam · Accepted Answer · 2016-05-09T01:20:27

This query might suit you needs:

MATCH p=(n)-[rels:PATH_TO*]->(n)
WITH p, REDUCE(s = 0, x IN rels | s + x.distance) AS dist
WITH p, MIN(dist) AS d
ORDER BY d
LIMIT 1
RETURN RELATIONSHIPS(p), d;

It finds all directed cyclic paths with PATH_TO relationships; calculates the total distance of each path; gets one path (out of potentially many) with the shortest total distance; and returns all of its relationships, along with the total distance.

Note: This query can take a very long time for large graphs. If so, you can try to put a reasonable upper bound on the variable-length pattern. For example, replace [rels:PATH_TO*] with [rels:PATH_TO*..5].

How to search the shortest distance between a set of nodes using Cypher

1 Answers