Floyd-Warshall algorithm: Difference between revisions

Content deleted Content added

Inline

@@ Line 635: / Line 635: @@
 <lang jq>def fwi:
   . as $weights
+  | keys_unsorted as $nodes
   # construct the dist matrix
-  | reduce ($weights|keys[]) as $u ({};
+  | reduce $nodes[] as $u ({};
-      reduce ($weights|keys[]) as $v (.;
+      reduce $nodes[] as $v (.;
         .[$u][$v] = infinite))
-  | reduce ($weights|keys[]) as $u (.; .[$u][$u] = 0 )
+  | reduce $nodes[] as $u (.; .[$u][$u] = 0 )
-  | reduce ($weights|keys[]) as $u (.;
+  | reduce $nodes[] as $u (.;
-      reduce ($weights[$u]|keys[]) as $v (.;
+      reduce ($weights[$u]|keys_unsorted[]) as $v (.;
         .[$u][$v] = $weights[$u][$v] ))
-  | reduce ($weights|keys[]) as $w (.;
+  | reduce $nodes[] as $w (.;
-      reduce ($weights|keys[]) as $u (.;
+      reduce $nodes[] as $u (.;
-        reduce ($weights|keys[]) as $v (.;
+        reduce $nodes[] as $v (.;
 	  (.[$u][$w] + .[$w][$v]) as $x
 	  | if .[$u][$v] > $x then .[$u][$v] = $x
-	    else . end ))) ;
+	    else . end )))
+;
 weights | fwi</lang>