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