Floyd Warshall 算法未按预期工作

Question

我正在尝试在 python 3 中实现 Warshall 算法，以创建一个矩阵，每个点之间的距离最短。

这应该是一个简单的实现，我制作了一个矩阵并用每个点之间的距离填充它。

但是，我得到了错误的结果，我不知道我的实现有什么问题。

#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。我错过了什么？

Answer 1

发现问题有点棘手，但是对您的程序进行简单的逐个更改跟踪可以发现问题：

        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 博客寻求帮助。

Floyd Warshall 算法未按预期工作

Floyd Warshall algorithm not working as intended

python

algorithm

floyd-warshall