cancel
Showing results for 
Search instead for 
Did you mean: 

ShortestPath

The picture shown below describes a section from a family tree.
The nodes N and O have one child R.
N has Mother J.
O has Mother K.
O and K both have D as Mother.
I'm trying to find the shortestPath between the nodes N and O, but I want to exclude the path N->R->O (a path with length 2).
The path I'm looking for is N -> J -> D -> K -> O (a path with length 4).
How can I construct a query to achieve this? I plan to run the query on the entire graph (>10.000 nodes), so it would be nice if it performed reasonably well.

2 REPLIES 2

koji
Ninja
Ninja

Hi @christian.longberg

How about this simple query.
If the hop count is small, the search speed will not be a problem.

MATCH p1=(n:Person {name: 'N'})-[:MOTHER*..2]->(mother:Person),
      p2=(d:Person {name: 'O'})-[:MOTHER*..2]->(mother)
RETURN p1,p2

CREATE (n:Person {name:'N'}),
       (j:Person {name:'J'}),
       (d:Person {name:'D'}),
       (k:Person {name:'K'}),
       (o:Person {name:'O'}),
       (r:Person {name:'R'})
CREATE (r)-[:MOTHER]->(n)-[:MOTHER]->(j)-[:MOTHER]->(d),
       (r)-[:MOTHER]->(o)-[:MOTHER]->(k)-[:MOTHER]->(d)
CREATE (r)<-[:OFFSPRING]-(n)<-[:OFFSPRING]-(j)<-[:OFFSPRING]-(d),
       (r)<-[:OFFSPRING]-(o)<-[:OFFSPRING]-(k)<-[:OFFSPRING]-(d);

Thank you for your reply @koji!
I should have mentioned that the goal is to calculate the shortest path between all nodes in the (full) graph with one query. Something like this:

Match p=shortestPath((d1:Person)-[*]-(d2:Person))
Return d1.id, d2.id, length(p)

The problem with this is that the actual shortest path between two parents is via their child, as in the example. The general rule could be that a starting node should never traverse via a child (offspring) when finding the shortest path to all other nodes.

Nodes 2022
Nodes
NODES 2022, Neo4j Online Education Summit

On November 16 and 17 for 24 hours across all timezones, you’ll learn about best practices for beginners and experts alike.