# Retrieving shortest paths from Graphs.jl

**URL:** <https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539>\
**Category:** General Usage\
**Tags:** graphs\
**Created:** [July 7, 2025, 4:28pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539 "2025-07-07T16:28:41Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![GRASP\_lover123](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/grasp_lover123/32/217618_2.png) [@GRASP\_lover123](https://discourse.julialang.org/u/GRASP_lover123)\
**Post date:** [July 7, 2025, 4:28pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/1 "2025-07-07T16:28:41Z")

</div>

Hi everybody,

I’m using Graphs.jl to get shortest paths using the a\* function, which give the list of edges in the shortest path from one node to another. Recently I’ve needed to get the shortest paths from all nodes to all nodes, however, functions that allow to do that, e.g. floyd\_warshall\_shortest\_paths(g, distmx=weights(g)), returns a `parents` matrix. Is there any function existing that can turn that into list of edges? (it’s not too hard to code, but I’m afraid of my abilities in getting best performance)

Thanks!

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 7, 2025, 4:58pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/2 "2025-07-07T16:58:02Z")

</div>

You can do something like this:

```julia
function reconstruct_path(parents::AbstractMatrix{<:Integer}, dep::Integer, arr::Integer)
    path = [arr]
    v = arr
    while parents[dep, v] != 0
        v = parents[dep, v]
        push!(path, v)
    end
    return reverse(path)
end

```

---

<div class="post-metadata">

**Author:** ![GRASP\_lover123](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/grasp_lover123/32/217618_2.png) [@GRASP\_lover123](https://discourse.julialang.org/u/GRASP_lover123)\
**Post date:** [July 8, 2025, 8:47am UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/3 "2025-07-08T08:47:38Z")

</div>

Thanks sir!

---

<div class="post-metadata">

**Author:** ![HSt](https://avatars.discourse-cdn.com/v4/letter/h/b38774/32.png) [@HSt](https://discourse.julialang.org/u/HSt)\
**Post date:** [July 9, 2025, 3:00pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/4 "2025-07-09T15:00:32Z")

</div>

I did something similar recently, my 2 cents here:

- instead of `push!`, `reverse`, one can use `pushfirst!`
- what if no path exisits? (underlying graph is not connected) I think the given implementation would return a single vertex “path” which may cause trouble at some other place.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 9, 2025, 4:02pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/5 "2025-07-09T16:02:30Z")

</div>

> [@HSt](#):
>
> instead of `push!`, `reverse`, one can use `pushfirst!`

I think `pushfirst!` is less efficient than `push!` memory-wise because it shifts every element of the vector forward?

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [July 9, 2025, 7:01pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/6 "2025-07-09T19:01:20Z")

</div>

No, it doesn’t, at least not all the time. Julia plays tricks with placing reserve space in both ends in order to avoid having to shift data more than necessary. I’m not sure where and if this is documented but it’s easy to verify experimentally that you don’t get quadratic complexity from repeated `pushfirst!`. You can also see in the `sizehint!` docstring that there is a concept of reserving space in the front.

```julia
If first is true, then any additional space is reserved before the start of the collection.

```

---

<div class="post-metadata">

**Author:** ![HSt](https://avatars.discourse-cdn.com/v4/letter/h/b38774/32.png) [@HSt](https://discourse.julialang.org/u/HSt)\
**Post date:** [July 10, 2025, 8:42am UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/7 "2025-07-10T08:42:52Z")

</div>

Apart from best implementation, I think some function like `reconstruct_path` should be part of `Graphs.jl`. I had to think a bit around the documentation and setting up a while loop every time is cumbersome.  
I can submit a PR next week.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 10, 2025, 11:51am UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/8 "2025-07-10T11:51:38Z")

</div>

It is part of Graphs.jl, it isn’t public yet though [Graphs.jl/src/shortestpaths/utils.jl at master · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/blob/master/src/shortestpaths/utils.jl)

---

<div class="post-metadata">

**Author:** ![GRASP\_lover123](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/grasp_lover123/32/217618_2.png) [@GRASP\_lover123](https://discourse.julialang.org/u/GRASP_lover123)\
**Post date:** [July 10, 2025, 12:44pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/9 "2025-07-10T12:44:46Z")

</div>

It’s a bit funny because in the astar implementation, it is done before sending the path back [Graphs.jl/src/shortestpaths/astar.jl at master · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/blob/master/src/shortestpaths/astar.jl)

Maybe it would be good to uniformise what these shortest path function send, and make the function to retrieve paths public ? 🫡

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 10, 2025, 1:15pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/10 "2025-07-10T13:15:04Z")

</div>

The difference is that A\* returns a single shortest path, so the underlying `parents` do not mean anything outside of that path. On the other hand, Dijkstra and friends are single-source/multiple-destination algorithms, so what they really return is a shortest path tree, rooted at the source but valid for all other vertices. That explains why the true object of interest is `parents` and not just one path

---

<div class="post-metadata">

**Author:** ![HSt](https://avatars.discourse-cdn.com/v4/letter/h/b38774/32.png) [@HSt](https://discourse.julialang.org/u/HSt)\
**Post date:** [July 11, 2025, 4:32pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/11 "2025-07-11T16:32:03Z")

</div>

Couldn’t Dijkstra’s have an optional `target` argument and return as soon as it is reached when given a `!isnothing(target)`? This would effectively “restrict” the implementation / variant to single-soure/single-target.

I call it multiple times (graph is modified between calls) to check existence of a path between two vertices `s, t` and was a bit upset that it’s doing extra work.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 11, 2025, 5:26pm UTC](https://discourse.julialang.org/t/retrieving-shortest-paths-from-graphs-jl/130539/12 "2025-07-11T17:26:57Z")

</div>

If you want that you might as well do A\* with a zero heuristic, that’s algorithmically equivalent (although the implementations may differ).  
In theory we could also have bidirectional dijkstra for that, I believe there’s an open issue or even PR