cancel
Showing results for 
Search instead for 
Did you mean: 

Quickly list shortest paths between 2 nodes

deeet
Node

Hi there,

I'm new with neo4j and looking for a way to find a list of shortest paths between 2 nodes.

 

(:Article { id: 1 })
(:Article { id: 2 })
(:Article { id: 3 })
(:Article { id: 4 })
(:Article { id: 5 })

MATCH(a:Article), (b:Article)
WHERE a.id = 1 and b.id = 2
CREATE (a)-[r:LINK { position: 1}]->(b)
...

 

So in total there ~5 millions of nodes and 120 millions of such simple relations.
Nodes ids are indexed with Btree index.
Neo4j is running on AWS server with 4 vCPUs and 8 RAM.
Not all nodes are directly linked, but by their child relations they do.

General goal is to find list of shortest paths between 2 nodes sorted by depth and sum of positions.

I have tried everything from https://neo4j.com/docs/graph-data-science/current/algorithms/pathfinding/
and as i understand https://neo4j.com/docs/graph-data-science/current/algorithms/yens/ should work for me, but if i  change k to 3 or more it begin to work 1 minute and more. 

https://neo4j.com/docs/cypher-manual/current/execution-plans/shortestpath-planning/
This one works really very fast, but it returns just 1 path.

allShortestPaths also works slow for depth > 3.

Could somebody please advice how to quickly achieve list of shortest paths or point into right direction?

Thank you in advance.

0 REPLIES 0
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.