Алгоритм Флойда Уоршалла не работает должным образом

Я пытаюсь реализовать алгоритм Варшалла в python 3, чтобы создать матрицу с кратчайшим расстоянием между каждой точкой.

Предполагается, что это простая реализация, я создаю матрицу и заполняю ее расстоянием между каждой точкой.

Однако я получаю неправильный результат и не знаю, в чем проблема с моей реализацией.

#number of vertex (N), number of connections(M)
N, M = 4,4;
#my matrix [A,B,C] where A and B indicates a connection
#from A to B with a distance C 
A = [[0,1,2],[0,2,4],[1,3,1],[2,3,5]];
#matrix alocation
inf = float("inf");
dist = [[inf for x in range(N)] for y in range(M)];

#set distances from/to the same vertex as 0
for vertex in range(N):
    dist[vertex][vertex] = 0;
#set the distances from each vertex to the other
#they are bidirectional. 
for vertex in A:
    dist[vertex[0]][vertex[1]] = vertex[2];
    dist[vertex[1]][vertex[0]] = vertex[2];

#floyd warshall algorithm
for k in range(N):
    for i in range(N):
        for j in range(N): 
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[1][j] = dist[i][k] + dist[k][j];
print(dist);

Ожидаемая матрица по первому индексу (dist [0]):

[0, 2, 4, 3]

Фактический результат:

[0, 2, 4, инф]

почему-то на dist [0] [3] продолжает получать inf вместо 3. Что мне не хватает?


python algorithm floyd-warshall
person Helio Ramos    schedule 18.10.2019    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Это немного сложно обнаружить, но простая трассировка вашей программы от одного изменения к другому выявляет проблему:

        if dist[i][j] > dist[i][k] + dist[k][j]:
            dist[1][j] = dist[i][k] + dist[k][j];
                 ^  This should be i, not 1

Вы изменяете расстояние от узла 1 до целевого узла; а не из исходного узла. Ваша результирующая матрица расстояний

[0, 2, 4, 3]
[2, 0, 6, 1]
[4, 6, 0, 5]
[3, 1, 5, 0]

Обратитесь за помощью к этому прекрасному блогу debug.

person Prune    schedule 18.10.2019
comment
Братан, ты такой спаситель, я терял из-за этого волосы, я, должно быть, проверял эту строчку как минимум 100 раз и не заметил там «1». Большое спасибо - person Helio Ramos; 18.10.2019