/*
  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
}

export { FloydWarshall }

// 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] ]

// FloydWarshall(
//     [[0, 1, 2, Infinity],
//       [1, 0, Infinity, Infinity],
//       [2, Infinity, 0, 1],
//       [Infinity, Infinity, 1, 0]
//     ]
//   )