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)