弗洛伊德·沃歇尔算法无法按预期工作

Question

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

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

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

#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， inf]

出于某种原因，我在 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]

请参阅这个可爱的调试博客以获取帮助。