Retrieving shortest paths from Graphs.jl

General Usage
1

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!

2

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
1 Like
3

Thanks sir!

4

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.
5

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