Retrieving shortest paths from Graphs.jl

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!

You can do something like this:

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
2 Likes

Thanks sir!

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.

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

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.

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

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.

1 Like

It is part of Graphs.jl, it isn’t public yet though Graphs.jl/src/shortestpaths/utils.jl at master · JuliaGraphs/Graphs.jl · GitHub

1 Like

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

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

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

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.

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