Алгоритм Дейкстры с матрицей смежности - PullRequest
Новая
       4

Алгоритм Дейкстры с матрицей смежности

3 голосов
/ 26 мая 2019

Я пытаюсь реализовать следующий код из здесь , но он не будет работать правильно.

То, что я хочу, - это кратчайшие пути пути от источника ко всем узлам, а также к предшественникам. Кроме того, я хочу, чтобы входные данные графа представляли собой матрицу смежности, которая содержит все веса ребер.

Я пытаюсь заставить его работать только в одной функции, поэтому мне нужно переписать его. Если я прав, исходный код вызывает другие функции (например, из graph.jl).

Я не совсем понимаю, как переписать цикл for, который вызывает функцию adj ().

Кроме того, я не уверен, правильно ли введены данные в том же коде, что и сейчас. 

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 и предшествующие элементы в другом векторном пред.

Прямо сейчас я получаю

ОШИБКА: тип Массив не имеет узлов полей

Stacktrace: [1] getproperty (:: Any, :: Symbol) в. \ Sysimg.jl: 18

Я думаю, мне нужно переписать это немного больше.

Я благодарен за любую помощь.

1 Ответ

1 голос
/ 27 мая 2019

Предполагая, что graph[i,j] - это длина пути от i до j (ваш график направлен на ваши данные), и это Matrix с неотрицательными записями, где 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

(я не проверял это подробно, поэтому, пожалуйста, сообщите, если вы обнаружите какие-либо ошибки)

...