python - Python中的弗洛伊德算法

Question

我不确定如何在以下程序中实现弗洛伊德算法。它必须在第 466 页打印一个表示该图的 5x5 数组，并包括一个计数器，该计数器用于在执行算法时打印比较的总数——“if”结构的每次执行都算作一次比较。

有谁知道如何启动这个程序？我不知道如何开始。

Answer 1

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

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]

Answer 2

从您链接到的页面翻译，

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 的准确翻译。更好，更多的 Pythonic 代码也是可能的 - 参见，例如 5xum 的答案，它使用该range函数而不是手动增加循环计数器。

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