Floyd Warshall Algorithm
Given and said to Warshall, "Find the shortest path between all pairs of vertices in a weighted graph with positive or negative edge weights, but beware of negative cycles!"
Constraints:
- The graph can have negative weight edges.
- The graph does not contain any self-loops.
- The graph does not contain any parallel edges.
Examples:
Input: [[0, 5, Infinity, 10], [Infinity, 0, 3, Infinity], [Infinity, Infinity, 0, 1], [Infinity, Infinity, Infinity, 0]]
Output: [[0, 5, 8, 9], [Infinity, 0, 3, 4], [Infinity, Infinity, 0, 1], [Infinity, Infinity, Infinity, 0]]
Explanation: The shortest path between each pair of vertices is calculated and stored in the resulting matrix.
Solutions
Floyd Warshall Algorithm
The Floyd Warshall algorithm works by considering each vertex as an intermediate step in the shortest path between each pair of vertices. It iteratively updates the shortest path between each pair of vertices by considering all possible intermediate vertices.
function floydWarshall(graph) {
let n = graph.length;
for (let k = 0;
k < n;
k++) {
for (let i = 0;
i < n;
i++) {
for (let j = 0;
j < n;
j++) {
if (graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
return graph;
}Follow-up:
How would you modify the algorithm to handle negative cycles?
