
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