Алгоритм Флойда Варшалла с матрицей смежности - PullRequest
Новая
       7

Алгоритм Флойда Варшалла с матрицей смежности

1 голос
/ 02 июля 2019

Я пытаюсь реализовать алгоритм Флойда Уоршалла, но он не будет работать правильно.

Что мне нужно, так это кратчайшие расстояния пути от одной вершины до другой, записанные в матрице d, и предшественники вматрица пред.Входные данные представляют собой матрицу смежности, которая содержит все веса ребер. 

function FloWa(C)

N = size(C)
n = min(C[1],C[2])

pred = -1*ones(C[1],C[2])
d = C

for k in 1:n
    for i in 1:n
        for j in 1:n
            if d[i,j] > d[i,k] + d[k,j]
                if pred[i,k] == -1
                    pred[i,j] = k
                else
                    pred[i,j] = pred[k,j]
                end
                d[i,j] = d[i,k] + d[k,j]
            end
            if i == j && d[i,i] < 0
                    println("negative Dicycle")
            end
        end
    end
end
return d, 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]

, я не получаю правильных результатов.

Для di получить ту же матрицу, что и A, и pred печатается как Array {Float64} (0,1).

1 Ответ

1 голос
/ 03 июля 2019

Я не проверял реализацию алгоритма, но вы, похоже, неправильно инициализируете pred и d. Вот способ сделать это, я полагаю, вы с отступом: 

n = size(C, 1) # get number of rows in C
@assert n == size(C, 2) # make sure that C is square or throw an error
pred = fill(-1, size(C)) # fill pred with -1 and make it have the same size as C
d = copy(C) # d is a copy of C
...