cancel
Showing results for 
Search instead for 
Did you mean: 

Head's Up! Site migration is underway. Phase 2: migrate recent content

Find next shortest path

MathiasGraabeck
Node Link

I want to find a couple of paths between 2 nodes. I don't just want the shortest path or all paths with the shortest length (allShortestPaths). I need all the shortest paths and the next shortest paths. Since it is not possible to set allShortestPaths with minimal length different from 0/1.

allShortestPaths(...) does not support a minimal length different from 0 or 1

It could be solved with projections or apoc.path.expandConfig, however we have a database with 14 million nodes and 56 million relationships, so when I tried doing this, we could deliver paths with lengths of 4 in 20-30 seconds and lengths of more than 4 was not possible. Is there a way to find a subset of all paths that are shortest, but also fast to execute?

Lets say my source node is A, and target node is C, and I wanted the 3 shortest paths, the 3 paths would then be:
(A-C), (A-B-C), (A-B-E-C)

MathiasGraabeck_0-1669118673556.png

1 REPLY 1

MathiasGraabeck
Node Link

I figured that yen's algorithm would be very suitable after I tried using projections (which was pretty fast)
https://neo4j.com/docs/graph-data-science/current/algorithms/yens/