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)

*Related*