Categories

# 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)