# Shortest Paths algorithms

**URL:** <https://community.neo4j.com/t/shortest-paths-algorithms/19733>\
**Category:** Graph Data Science / Graph Analytics\
**Tags:** paths\
**Created:** [June 9, 2020, 12:45pm UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733 "2020-06-09T12:45:15Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![mayassia](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mayassia/32/3913_2.png) [@mayassia](https://community.neo4j.com/u/mayassia)\
**Post date:** [June 9, 2020, 12:45pm UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733/1 "2020-06-09T12:45:15Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mark.needham](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mark.needham/32/104_2.png) [@mark.needham](https://community.neo4j.com/u/mark.needham)\
**Post date:** [June 9, 2020, 1:05pm UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733/2 "2020-06-09T13:05:22Z")

</div>

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](https://neo4j.com/docs/graph-data-science/current/)) so that I can see why you aren't getting the same results?

---

<div class="post-metadata">

**Author:** ![mayassia](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mayassia/32/3913_2.png) [@mayassia](https://community.neo4j.com/u/mayassia)\
**Post date:** [June 9, 2020, 1:34pm UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733/5 "2020-06-09T13:34:13Z")

</div>

The problem that all pair shortest paths algorithm does not return paths, only distance

```auto
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:

```auto
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.

---

<div class="post-metadata">

**Author:** ![alicia.frame](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/alicia.frame/32/4507_2.png) [@alicia.frame](https://community.neo4j.com/u/alicia.frame)\
**Post date:** [June 10, 2020, 4:17pm UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733/6 "2020-06-10T16:17:56Z")

</div>

Try using [Yen's K shortest paths](https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/yen-s-k-shortest-path/) (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.

---

<div class="post-metadata">

**Author:** ![mayassia](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mayassia/32/3913_2.png) [@mayassia](https://community.neo4j.com/u/mayassia)\
**Post date:** [June 14, 2020, 6:40pm UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733/7 "2020-06-14T18:40:35Z")

</div>

Thank you. Finally, my problem was solved

---

<div class="post-metadata">

**Author:** ![natakorn.chanpetch](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/natakorn.chanpetch/32/13789_2.png) [@natakorn.chanpetch](https://community.neo4j.com/u/natakorn.chanpetch)\
**Post date:** [September 11, 2020, 4:37am UTC](https://community.neo4j.com/t/shortest-paths-algorithms/19733/8 "2020-09-11T04:37:51Z")

</div>

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