时间戳

首页 > 解决方案 > 具有邻接矩阵的 Dijkstra 算法

julia - 具有邻接矩阵的 Dijkstra 算法

问题描述

我正在尝试从此处实现以下代码，但它无法正常工作。

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

我试图让它只在一个函数中工作，所以我必须重写它。如果我是对的，那么原始代码会调用其他函数（例如来自 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 中的距离和另一个 vectore pred 中的前辈。

现在我得到

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

堆栈跟踪：[1] getproperty(::Any, ::Symbol) at .\sysimg.jl:18

我想我必须再重写一点。

我很感谢任何帮助。

标签： julia

解决方案

假设这graph[i,j]是从ito的路径长度j（您的图表直接查看您的数据），并且它是一个Matrix非负条目，其中表示从to0没有边，您的代码的最小重写应该是这样的：ij

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

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

推荐阅读