如何实现Floyd算法？

Question

我必须用Python实现Floyd算法。在

我必须使用这个代码模板。 邻接矩阵是在练习中给出的，但是我必须把它转换成双矩阵，如下所示。最后在双矩阵上执行Floyd算法。在

我现在的主要问题是将邻接矩阵转换成双矩阵，它包含距离和前一个结。在

import math
import pprint as pp

def createBiMatrix(mat):


bimatrix = [] 


pass

return bimatrix



def updateForNode(bimat, node):

pass;




return bimat



def determinePath(bimat, start, end):


recursionStep(bimat, start, end)

print(end)


def recursionStep(bimat, start, end):

pass

return


if __name__ == "__main__":

matsize = 5

mat = [matsize * [math.inf] for i in range(matsize)]
mat[0][0] = 0
mat[0][1] = 2
mat[0][2] = 10
mat[1][1] = 0
mat[1][2] = 3
mat[1][3] = 12
mat[2][0] = 10
mat[2][1] = 3
mat[2][2] = 0
mat[2][4] = 1
mat[3][1] = 12
mat[3][3] = 0
mat[4][2] = 1
mat[4][3] = 6
mat[4][4] = 0

bim = createBiMatrix(mat)
pp.pprint(bim)


for i in range(matsize):
    bim = updateForNode(bim, i)
    print("Step " + str(i) + ":")
    pp.pprint(bim)



start = 0
end = 3
print("shortest path (" + str(start) + " nach " + str(end) + "):")
determinePath(bim, start, end)

Answer 1

假设bimatrix是一个在索引i上存储到顶点{}和前一个顶点的最短路径的列表

createBiMatrix(mat):
  bimatrix = [(math.inf, None) for _ in range(len(mat))]

  for from in range(len(mat)):
    for to in range(len(mat[0])):
      if mat[from][to] < bimatrix[to][0]:
        bimatrix[to] = (mat[from][to], from)
  return bimatrix