I have to implement the Floyd Algorithm in Python.

I have to use this template of code. The adjacency Matrix is given in the exercise however I have to convert it into the bimatrix as seen below. Then lastly the Floyd algorithm Needs to be executed onto the bimatrix.

My main Problem right now consists of converting the adjacency Matrix into the bimatrix, which contains the distance as well as the previous Knot.

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)

1 Answers

0
Peter Kovary On

Assuming, that the bimatrix is meant to be a list that on index i stores shortest path to vertex i and the preceding vertex

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