cancel
Showing results for 
Search instead for 
Did you mean: 

kShortestPaths with k=1 gives different results to shortestPath

tdudgeon
Node

I'm want to use the kShortestPaths algorithm to generate the best shortest paths, but it's behaving strangely.

I tried setting k to 1, expecting that would give the same result as the shortestPath algorithm, but it doesn't. The shortestPath algorithm gives what looks like the right results with 6 edges. The kShortestPaths with k=1 gave a huge list of nodeIds (so big the browser truncated it), and a path that was null. If I also add maxDepth=20 I get a much shorter path, but not the same one as the one from shortestPath (it has 9 nodes, 8 edges).

If I do k=3 I get 3 paths, but the second is shorter than the first. And all are longer than with k=1.
This is using GDS version 1.1.6 and Neo4j 3.5.25.

No weights are involved so the cost should just be the number of edges?

A typical query is

MATCH (a:F2 {smiles: 'CC(=O)NCCc1c[nH]c2ccc(F)cc12'}),(b:F2 {smiles: 'Cc1nnc(CN2CCC=C(F)C2)s1'})
CALL gds.alpha.kShortestPaths.stream({startNode: a, endNode: b, nodeProjection: 'F2', k: 1, maxDepth: 20,
relationshipProjection: {FRAG: {type: 'FRAG', orientation: 'UNDIRECTED' }}})
YIELD nodeIds RETURN nodeIds;
2 REPLIES 2

sam_gijare
Graph Buddy

Please upgrade the Neo4j and GDS library versions and then retry again to see if it is gives proper results.

tdudgeon
Node

Yes, I tried with Neo 4.2.1 and GDS 1.5.0 and the behaviour is much better.
Thanks for the suggestion.

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.