Floyd Warshall Algorithm
All-Pairs Shortest Path

Problem Statement

The Floyd Warshall Algorithm solves the problem of finding the shortest path between all pairs of vertices in a weighted, directed graph.

The graph is given as an n × n adjacency matrix matrix, where matrix[i][j] represents the weight of the edge from node i to node j. A value of -1 indicates that there is no direct edge between the two nodes.

Your task is to compute the shortest distances between every pair of nodes. If there is no path between two nodes, the corresponding distance should remain -1.

Algorithm Steps

1. Let matrix be the input adjacency matrix of size n × n.
2. Initialize a distance matrix dist with the same values as matrix.
3. Replace all -1 values (except diagonals) in dist with Infinity.
4. For each node k from 0 to n-1:
1. For each node i from 0 to n-1:
2. For each node j from 0 to n-1:
3. If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j].
5. Convert all Infinity values in dist back to -1.

Code

function floydWarshall(matrix) {
  const n = matrix.length;
  const dist = Array.from({ length: n }, (_, i) =>
    matrix[i].map(val => (val === -1 && i !== matrix[i].indexOf(val) ? Infinity : val))
  );

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // Convert Infinity back to -1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dist[i][j] === Infinity) dist[i][j] = -1;
    }
  }

  return dist;
}

const matrix = [
  [0, 3, -1],
  [-1, 0, 1],
  [4, -1, 0]
];

console.log("Shortest distances:", floydWarshall(matrix));