cancel
Showing results for 
Search instead for 
Did you mean: 

Trying to get shortest path for all source, target combinations (Djikstra vs Alpha)

denizn
Node
I am using below two different approaches to come up with the shortest paths across all target and source combinations. I have 64 gbs of memory and am expecting "all shortest paths" to take shorter; however, iterating through Djikstra single source algorithm for each node somehow works faster than that algo. 
 
I'm wondering if I'm doing something wrong... Any help would be appreciated.
  • All Shortest Paths:
CALL gds.alpha.allShortestPaths.stream('cypherGh3', {
relationshipWeightProperty: 'cost',
concurrency : 4
})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance

MATCH (source:Loc) WHERE id(source) = sourceNodeId
MATCH (target:Loc) WHERE id(target) = targetNodeId
WITH source, target, distance
WHERE source <> target
AND source.name STARTS WITH 'BIN'
AND target.name STARTS WITH 'BIN'

RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC, source ASC, target ASC
  • Djikstra single source shortest path (repeated for all source nodes):
CALL gds.alpha.allShortestPaths.stream('cypherGh3', {
relationshipWeightProperty: 'cost',
concurrency : 4
})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance

MATCH (source:Loc) WHERE id(source) = sourceNodeId
MATCH (target:Loc) WHERE id(target) = targetNodeId
WITH source, target, distance
WHERE source <> target
AND source.name STARTS WITH 'BIN'
AND target.name STARTS WITH 'BIN'

RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC, source ASC, target ASC
3 REPLIES 3

TrevorS
Community Team
Community Team

Hello @denizn 

Thank you for posting to the Community. I see that you still havnt received any feedback on your question. Are you still looking for assistance or were you able to resolve this?

If you were able to resolve the issue, can you please reply back with your solution so that others can refer to your solution?
If you are still looking for assistance, please let me know so I can try to get additional eyes on your post!
Thanks,

TrevorS
Community Specialist

Hello @denizn ,
the code you posted for Dijkstra and allShortestPath are the same.
Maybe you wanted to post a different query? For the allshortest path dijkstra version you should use

CALL gds.allShortestPaths.delta.stream

``(https://neo4j.com/docs/graph-data-science/current/algorithms/delta-single-source/)

It also looks like you are not using the latest version of GDS