Floyd Warshall Algorithm

The Floyd Warshall Algorithm is used to find the shortest distance between all pairs in a weighted graph with positive or negative edges. It makes use of Dynamic Programming.

• If A, B, C are vertices, then this algorithm checks for the following
  if (AC > AB + BC)
  AC  = AB + BC;

Consider a graph represented in the form of an adjacency matrix as the input.

const inf = 9999;
const graph = [
  [0, 5, 2, 10],
  [10, 0, 5, inf],
  [inf, inf, 0, 8],
  [inf, 1, 3, 0]
];

let floydWarshall = (graph) => {
  let mem = [];
  const size = graph.length;
  for (var i = 0; i < size; i++) {
    mem[i] = graph[i].slice();
  }
  for (var k = 0; k < size; k++) {
    for (var i = 0; i < size; i++) {
      for (var j = 0; j < size; j++) {
        if (mem[i][j] > mem[i][k] + mem[k][j]) {
          mem[i][j] = mem[i][k] + mem[k][j];
        }
      }
    }
  }
  console.log(mem);
};

floydWarshall(graph);

Output

[0, 5, 2, 10]
[10, 0, 5, 13]
[19, 9, 0, 8]
[11, 1, 3, 0]

Demo

if n = Number of edges.
Runtime Complexity
O(n^3)

Space Complexity
O(n^2)