# Shortest Paths algorithms

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.

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?

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.

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.

Thank you. Finally, my problem was solved

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