Lekcja – Algorytm Floyda Warshalla

```names = ['A', 'B', 'C', 'D', 'E']
graph = [  # A   B   C   D   E
[0,  2,  0,  4,  0], # A
[0,  0,  3,  3,  0], # B
[0,  0,  0,  0,  2], # C
[0,  0,  -1, 0,  4], # D
[0,  0,  0,  0,  0]  # E
]

def print_matrix(matrix, names):
N = len(matrix)
line = '    '
for n in names:
line += f'{n:>4}'
print(line)
for row in range(N):
line = f'{names[row]:>4}'
for col in range(N):
line += f'{matrix[row][col]:>4}'
print(line)

N = len(graph)
costs_matrix = [[float('inf') for x in range(N)] for x in range(N)]
parent_matrix = [['' for x in range(N)] for x in range(N)]

for i in range(N):
for j in range(N):
if i == j:
costs_matrix[i][j] = 0
parent_matrix[i][j] = i
elif graph[i][j] != 0:
costs_matrix[i][j] = graph[i][j]
parent_matrix[i][j] = i

for p in range(N):
for i in range(N):
for j in range(N):
if costs_matrix[i][j] > costs_matrix[i][p] + costs_matrix[p][j]:
costs_matrix[i][j] = costs_matrix[i][p] + costs_matrix[p][j]
parent_matrix[i][j] = parent_matrix[p][j]

print_matrix(costs_matrix, names)
print_matrix(parent_matrix, names)

start_node = 0
end_node = 4

while end_node != start_node:
print(names[end_node])
end_node = parent_matrix[start_node][end_node]
else:
print(names[end_node])

for i in range(N):
for j in range(N):
if parent_matrix[i][j] != '':
parent_matrix[i][j] = names[parent_matrix[i][j]]

print_matrix(parent_matrix, names)```

Lab

```names = ['CP', 'S', 'DR', 'SS', 'F', 'A', 'AP']
graph = [  # CP  S   DR SS   F   A   AP
[ 0, 10,  0, 15,  0,  0,  0], # CP
[ 0,  0, 20,  0,  0,  0,  0], # S
[ 0,  0,  0,  0, -5,  5,  0], # DR
[ 0,  0,  5,  0,  0,  0, 50], # SS
[ 0,  0,  0,  0,  0,  0, 10], # F
[ 0,  0,  0,  0,  0,  0, 10], # A
[ 0,  0,  0,  0,  0,  0,  0]  # AP
]

def print_matrix(matrix, names):
N = len(matrix)
line = '    '
for n in names:
line += f'{n:>4}'
print(line)
for row in range(N):
line = f'{names[row]:>4}'
for col in range(N):
line += f'{matrix[row][col]:>4}'
print(line)

N = len(graph)
costs_matrix = [[float('inf') for x in range(N)] for x in range(N)]
parent_matrix = [['' for x in range(N)] for x in range(N)]

for i in range(N):
for j in range(N):
if i == j:
costs_matrix[i][j] = 0
parent_matrix[i][j] = i
elif graph[i][j] != 0:
costs_matrix[i][j] = graph[i][j]
parent_matrix[i][j] = i

for p in range(N):
for i in range(N):
for j in range(N):
if costs_matrix[i][j] > costs_matrix[i][p] + costs_matrix[p][j]:
costs_matrix[i][j] = costs_matrix[i][p] + costs_matrix[p][j]
parent_matrix[i][j] = parent_matrix[p][j]

print_matrix(costs_matrix, names)

for i in range(N):
for j in range(N):
if parent_matrix[i][j] != '':
parent_matrix[i][j] = names[parent_matrix[i][j]]

print_matrix(parent_matrix, names)```