Julia ：从 Graphs.jl 中的 Dijkstra 函数获取完整路径

Question

是否有可能使用 Graphs.jl 模块中的 Dijkstra algorithm 获取从源顶点到目标顶点的完整路径？

有一个 update_vertex!(visitor, u, v, d) 方法在更新到顶点的距离时被调用。只有找到属于最短路径的新顶点才更新距离吗？我不太确定。

谢谢。

编辑：

根据文档，可以使用具有属性 dists 和 nexts 的 Floyd-Warshall algorithm 重建最短路径，但我不是确定如何。我想运行它在我的 GenericGraph.

有什么想法吗？

Answer 1

正如@DanGetz 指出的那样，算法的结果包含一个名为 parents 的字段。每个节点在到达它之前都有最后一个访问过的节点（即最短路径中的 parent）。使用每个节点的父节点，您可以使用简单的递归函数回溯每个节点的最短路径：

spath(x, r, s) = x == s ? x : [spath(r.parents[x], r, s) x]

其中 r 是 Dijkstra 算法的结果，s 是传递给它的源。

每个节点的最短路径可以通过列表推导得到。在下面找到 example in the documentation:

的结果

julia> [spath(x, r, 1) for x in g.vertices]
5-element Array{Any,1}:
 1                               
  1x3 Array{Int64,2}:
 1  3  2   
  1x2 Array{Int64,2}:
 1  3      
  1x4 Array{Int64,2}:
 1  3  2  4
  1x3 Array{Int64,2}:
 1  3  5

可能有更好的算法来做到这一点（即一些动态编程方法来记住大图的路径），但作为一个例子，递归方法可以完成这项工作。

A quick 递归代码适用于您的字典，每个最短路径有多个父项：

function spath(current, parents, source, current_path)
    if current == source || isempty(parents[current])
        return Any[[current; current_path]]
    end

    results = []
    for node in parents[current]
        results = [spath(node, parents, source, [current; current_path]); results]
    end

    results
end

注意当前路径作为参数（它的副本）传递到叶节点（源），因此，returns 到达它时的整个最短路径。同样，它可能不是最有效的实现（我不是 julia guru），但它完成了工作。

以你的例子为例：

julia> parents = {2=>[1,3],3=>[1],1=>[]}
julia> [(i, spath(i, parents, 1, [])) for i in keys(parents)]
3-element Array{Tuple{Any,Array{Any,1}},1}:
 (2,Any[Any[1,3,2],Any[1,2]])
 (3,Any[Any[1,3]])           
 (1,Any[Any[1]])

Julia ：从 Graphs.jl 中的 Dijkstra 函数获取完整路径

Julia : getting whole path from Dijkstra function in Graphs.jl

algorithm

dijkstra

julia