CODEWITHSUNDEEP
neo4jcypher
Anshul
Anshul

Reputation: 211

Longest shortest path between any two nodes of a graph

I am trying to find two nodes that are furthest from each other in my Neo4j Database. For the purposes of my analysis, I am considering shortest distance between the two nodes as the distance between them. Therefore, the two nodes that are furthest will have longest shortest path between them. I am using the following syntax from Cypher to find the shortest node.

Given two nodes as shown in the Neo4j example documentation http://docs.neo4j.org/chunked/milestone/query-match.html#match-shortest-path, I can run the following Cypher query.

MATCH p = shortestPath((martin:Person)-[*..15]-(oliver:Person))
WHERE martin.name = 'Martin Sheen' AND oliver.name = 'Oliver Stone'
RETURN p

My database has over 1/2 million nodes. The brute force way will obviously take a long time. Is there any easy or faster way to get the two nodes?

[As an extra wrinkle .. the graph is weighted but this detail can be ignored.]

Upvotes: 4

Views: 5573

Answers (1)

Nicholas
Nicholas

Reputation: 7501

If I'm reading this correctly, you want all-pairs shortest path. This will give you a list with each node as a source and the shortest path to every other node. While it does do it by weight, you can simple use a weight of 1 for everything.

You'll have to implement this yourself in Java as Cypher doesn't have anything for this.

Upvotes: 5

Related Questions