Différences

Ci-dessous, les différences entre deux révisions de la page.

--- jour_tp_chemin:roy [2018/11/16 14:20] – créée 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 = "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>