Head's Up! These forums are read-only. All users and content have migrated. Please join us at community.neo4j.com.
06-09-2020 05:45 AM
Hello,
I want to compute shortest paths for all pairs in my graph. I tried to use all pairs shortest paths
and single shortest paths
but both do not return paths like apoc dijkstra.
I'm working in a graph with 4602
nodes and 80000
relationships. I can not use apoc dijkstra because it is very slow in my case.
Thank you.
06-09-2020 06:05 AM
Can you share the queries that you've written using apoc dijkstra and (presumably) the GDS Library (https://neo4j.com/docs/graph-data-science/current/) so that I can see why you aren't getting the same results?
06-09-2020 06:34 AM
The problem that all pair shortest paths algorithm does not return paths, only distance
Match (h:Hub:Airport),(a:Arrival)
where h.code <> a.code
Call apoc.algo.dijkstra(h,a,'2017-10>|BOARD_AT|CONNECT_TO>', 'duration_min') yield path as pH, weight as dur
return pH
So here I can get paths (pH)
The all pair shortest paths query is:
CALL algo.allShortestPaths.stream('duration_min', {
nodeQuery:'MATCH (n) RETURN id(n) as id',
relationshipQuery:'MATCH (n:Hub:Departure)-[r]-(p:Arrival) RETURN id(n) as source, id(p) as target, r.duration_min as weight',
graph:'cypher', defaultValue:1.0})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance
WHERE algo.isFinite(distance) = true
MATCH (source:Origin) where id(source) = sourceNodeId
MATCH (target:Airport) WHERE id(target) = targetNodeId
WITH source, target, distance WHERE source <> target
RETURN source.code AS source, target.code AS target, distance
ORDER BY distance DESC
Here I can return only distance but not the path.
06-10-2020 09:17 AM
Try using Yen's K shortest paths (it use's Djikstra's algorithm), and set k=1, and set path:true
. This will return the shortest path between your nodes as a path.
06-14-2020 11:40 AM
Thank you. Finally, my problem was solved
09-10-2020 09:37 PM
Your solution is using the Yen's K shortest paths or not?
(if it is not) Could you please share different solutions for me?
All the sessions of the conference are now available online