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