CODEWITHSUNDEEP
javaneo4jcypher
M4rk
M4rk

Reputation: 2272

neo4j Alternative path

I'm doing a simple routing software, and the classical need to achieve a "good product" is offering to the customer different path.

I'm using cypher, but as far as I know, it is not achievable.. I can only find "allShortestPath" of my graph and not "almost shortest".

My idea was executing multiple time dijkstra adding some weight on the first of the previous path, so it "probably" will look at another path. The problem is that I don't know how to let cypher evaluate temporary weghts on my graph.

I could even think to create a custom plugin using neo4j's java api, and I could use dijkstra algo directly with weight evaluator, but then I don't think I could get all possible paths, but only one

Thanks in advance for any advice

Upvotes: 1

Views: 400

Answers (2)

Michael Hunger
Michael Hunger

Reputation: 41676

There is work in progress for allowing dijkstra to return more than one path, currently it returns all shortest paths.

START n1=node(167), n2=node(169) 
MATCH p=shortestPath((n1)-[]-(n2))
WITH n1,n2,length(p)+1 as almost_shortest
MATCH p = (n1)-[*..3]-(n2) 
WHERE length(p) = almost_shortest 
RETURN p

I still you're best using a modified dijkstra or other path-finding algorithm that provides you with the number of paths.

With the traversal-description or bidirectional-traversal-description and custom PathEvaluators / PathExpander you can build whatever you want.

Upvotes: 0

commesan
commesan

Reputation: 526

What about getting the length of the shortest path and than ask neo4j for a path of that length+1.

Perhaps this will work for you:

START n1=node(167), n2=node(169) MATCH p = (n1)-[*..3]-(n2) WHERE length(p) = length(shortestPath((n1)-[]-(n2)))+1 RETURN p

You'd probably want to limit the maximum path length.

Upvotes: 1

Related Questions