julia - 带邻接矩阵的 Dijkstra 算法

Question

我正在尝试实现来自 here 的以下代码但它不会正常工作。

我想要的是从源到所有节点以及前驱节点的最短路径距离。另外，我希望图形的输入是一个包含所有边权重的邻接矩阵。

我试图让它只在一个函数中工作，所以我必须重写它。如果我是对的，原始代码会调用其他函数(例如来自 graph.jl)。

我不太明白如何重写调用 adj() 函数的 for 循环。

此外，我不确定输入的代码目前是否正确。

function dijkstra(graph, source)
    node_size = size(graph, 1)
    dist = ones(Float64, node_size) * Inf
    dist[source] = 0.0
    Q = Set{Int64}()  # visited nodes
    T = Set{Int64}(1:node_size)  # unvisited nodes
    pred = ones(Int64, node_size) * -1
    while condition(T)
        # node selection
        untraversed_nodes = [(d, k) for (k, d) in enumerate(dist) if k in T]
        if minimum(untraversed_nodes)[1] == Inf
            break # Break if remaining nodes are disconnected
        end
        node_ind = untraversed_nodes[argmin(untraversed_nodes)][2]
        push!(Q, node_ind)
        delete!(T, node_ind)
        # distance update
        curr_node = graph.nodes[node_ind]
        for (neigh, edge) in adj(graph, curr_node)
            t_ind = neigh.index
            weight = edge.cost
            if dist[t_ind] > dist[node_ind] + weight
                dist[t_ind] = dist[node_ind] + weight
                pred[t_ind] = node_ind
            end
        end
    end
    return dist, pred
end

所以如果我用下面的矩阵来尝试

A = [0 2 1 4 5 1; 1 0 4 2 3 4; 2 1 0 1 2 4; 3 5 2 0 3 3; 2 4 3 4 0 1; 3 4 7 3 1 0] 

和来源 2 我想获得向量 dist 中的距离和另一个向量 pred 中的前身。

现在我得到

错误:数组类型没有字段节点

Stacktrace: [1] getproperty(::Any, ::Symbol) at .\sysimg.jl:18

我想我必须再重写一下。

我很感激任何帮助。

Answer 1

假设 graph[i,j] 是从 i 到 j 的路径长度(您的图表直接查看您的数据)，并且它是一个具有非负项的矩阵，其中0表示从i到j没有边，您的代码的最小重写应该是这样的:

function dijkstra(graph, source)
    @assert size(graph, 1) == size(graph, 2)
    node_size = size(graph, 1)
    dist = fill(Inf, node_size)
    dist[source] = 0.0
    T = Set{Int}(1:node_size)  # unvisited nodes
    pred = fill(-1, node_size)
    while !isempty(T)
        min_val, min_idx = minimum((dist[v], v) for v in T)
        if isinf(min_val)
            break # Break if remaining nodes are disconnected
        end
        delete!(T, min_idx)
        # distance update
        for nei in 1:node_size
            if graph[min_idx, nei] > 0 && nei in T
                possible_dist = dist[min_idx] + graph[min_idx, nei]
                if possible_dist < dist[nei]
                    dist[nei] = possible_dist
                    pred[nei] = min_idx
                end
            end
        end
    end
    return dist, pred
end

(我还没有对它进行广泛的测试，所以如果你发现任何错误请报告)