Shortest Paths algorithms

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

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.

2

Can you share the queries that you've written using apoc dijkstra and (presumably) the GDS Library (The Neo4j Graph Data Science Library Manual v2.2 - Neo4j Graph Data Science) so that I can see why you aren't getting the same results?

5

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.

6

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.

7

Thank you. Finally, my problem was solved

8

Your solution is using the Yen's K shortest paths or not?
(if it is not) Could you please share different solutions for me?