Python中的Floyd算法

Question

我不确定如何在下面的程序中实现Floyd的算法。它必须打印一个5x5数组，该数组表示该图on page 466，并包含一个计数器，该计数器用于在执行算法时打印比较总数-“if”结构的每次执行都算作一个比较。在

有人知道怎么开始这个项目吗？我不知道怎么开始。在

Answer 1

从你链接的页面翻译过来的

k=0
while (k <= n-1):
    i=0
    while (i<=n-1):
        j=0
        while(j<=n-1):
            if(A[i,k] + A[k,j] < A[i,j]):
                A[i,j] = A[i,k] + A[k,j]
            j += 1
        i += 1
    k += 1

注：这是Python的确切翻译。 更好，更多的python代码也是可能的-参见，例如5xum的答案 它使用range函数，而不是手动递增循环计数器。在

还有A这里是一个二维矩阵（例如numpy ndarray）。 查看有关numpyhere的更多信息

Answer 2

以下是您链接的伪代码的一个转录。我几乎什么都没改变。在

for k in range(n):
    for i in range(n):
        for j in range(n):
            if A[i][k]+A[k][j]<A[i][j]:
                A[i][j]=A[i][k]+A[k][j]