import math
INFINI = math.inf
NEIGHBOURS = "neighbours"
def roy-floyd-warshall(graph):
distances = {}
steps = {}
for origin in graph:
steps[origin] = {}
distances[origin] = {}
for destination in graph:
steps[origin][destination] = None
distances[origin][destination] = INFINI
if destination in graph[origin][NEIGHBOURS]:
distances[origin][destination] = graph[origin][NEIGHBOURS][destination]
distances[origin][origin] = 0
for step in graph:
for origin in graph:
for destination in graph:
if distances[origin][step] + distances[step][destination] < distances[origin][destination]:
distances[origin][destination] = distances[origin][step] + distances[step][destination]
steps[origin][destination] = step
return steps, distances