Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | |||
jour_tp_chemin:roy [2018/11/16 14:42] – pprea | jour_tp_chemin:roy [2018/12/04 12:00] (Version actuelle) – pprea | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | <code python> | ||
+ | import math | ||
+ | INFINI = math.inf | ||
+ | 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 | ||
+ | | ||
+ | </ |