mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 15:39:42 +08:00
48 lines
1.3 KiB
JavaScript
48 lines
1.3 KiB
JavaScript
/*
|
|
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]
|
|
// ]
|
|
// )
|