CODEWITHSUNDEEP
neo4jcypher
Harold Chan
Harold Chan

Reputation: 809

Neo4j search for second shortest path

We know that we can get the shortest path between nodes by the following statement

MATCH p=allShortestPaths((a)-[*]->(b))

Is there any way to search for the second shortest path without exhaustive search?

Upvotes: 3

Views: 305

Answers (2)

Thennan
Thennan

Reputation: 898

You could find the shortest path in a subquery first and then find the paths that are longer than the shorter path.

CALL
{MATCH p=shortestPath((a)-[*]->(b))
RETURN length(p) as `shortPathLength`}
MATCH p=shortestPath((a)-[*]->(b))
WHERE length(p) > `shortPathLength`
RETURN p

Using SKIP or LIMIT and hardcoding a number to skip the first shortest path is likely to fetch undesired results in your use case if there are multiple shortest paths with the smallest number of hops.

Upvotes: 1

David Makogon
David Makogon

Reputation: 71118

There's no way to specify something like second shortest path via shortestPath() or allShortestPaths(). However: You could search for all paths, ordered by path length, and just limit the depth and number of items returned. For example:

MATCH p =(a)-[*2..5]-(b)
RETURN p, length(p)
order by length(p)
LIMIT 5;

You'd have to fine-tune this based on your knowledge of the domain (such as min # and max # of relationship hops). And you can further optimize with the addition of labels and relationship types.

Upvotes: 3

Related Questions