jour_tp_chemin:roy [WiKi informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

<code python>
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
    
</code>