Как реализовать алгоритм Флойда? - PullRequest
Новая
       21

Как реализовать алгоритм Флойда?

0 голосов
/ 06 мая 2019

Я должен реализовать алгоритм Флойда в Python.

Я должен использовать этот шаблон кода.Матрица смежности дана в упражнении, однако мне нужно преобразовать ее в биматрицу, как показано ниже.Затем, наконец, алгоритм Флойда должен быть выполнен на биматрице.

Моя главная проблема сейчас состоит в преобразовании матрицы смежности в биматрицу, которая содержит расстояние, а также предыдущий узел. 

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 Ответ

0 голосов
/ 06 мая 2019

Предполагается, что bimatrix должен быть списком, который в индексе i хранит кратчайший путь к вершине 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
...