Merge pull request TheAlgorithms#349 from c-utkarsh/add-floyd-warshall

raklaptudirm · web-flow · commit aaee62b6aa1e · 2021-05-23T13:38:04.000+05:30
Added FloydWarshall All Pairs Shortest Path Algo
diff --git a/Graphs/FloydWarshall.js b/Graphs/FloydWarshall.js
@@ -0,0 +1,48 @@
+/*
+  Source:
+    https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
+
+  Complexity:
+    O(|V|^3) where V is the set of vertices
+*/
+
+const FloydWarshall = (dist) => {
+  // Input:- dist: 2D Array where dist[i][j] = edge weight b/w i and j
+  // Output:- dist: 2D Array where dist[i][j] = shortest dist b/w i and j
+  const n = dist.length
+  for (let k = 0; k < n; k++) {
+    for (let i = 0; i < n; i++) {
+      for (let j = 0; j < n; j++) {
+        if (dist[i][j] > dist[i][k] + dist[k][j]) {
+          // dist from i to j via k is lesser than the current distance
+          dist[i][j] = dist[i][k] + dist[k][j]
+        }
+      }
+    }
+  }
+  return dist
+}
+
+const main = () => {
+  // For the following graph (edge weights are shown in brackets)
+  //  4       1       dist[1][2] = dist[2][1] = 1
+  //   \  (2)/ \      dist[1][3] = dist[3][1] = 2
+  //    \   /   \(1)  dist[1][4] = dist[4][1] = Infinity
+  //  (1)\ /     \    dist[3][4] = dist[4][3] = 1
+  //      3       2   dist[2][4] = dist[4][2] = Infinity
+  //                  dist[2][3] = dist[3][2] = Infinity
+  // Output should be:
+  // [ [0, 1, 2, 3],
+  //   [1, 0, 3, 4],
+  //   [2, 3, 0, 1],
+  //   [3, 4, 1, 0] ]
+  console.log(FloydWarshall(
+    [[0, 1, 2, Infinity],
+      [1, 0, Infinity, Infinity],
+      [2, Infinity, 0, 1],
+      [Infinity, Infinity, 1, 0]
+    ]
+  ))
+}
+
+main()
