Floyd-Warshall Algorithm

Floyd-Warshall algorithm is a classic algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). It can be used to find the shortest paths between all pairs of vertices in a graph.

Algorithm Overview

The algorithm works by considering all pairs of vertices and systematically trying all possible paths between each pair to find the shortest path. It does this using dynamic programming.

Steps of the Algorithm

1. Initialization: Create a distance matrix dist, where dist[i][j] represents the shortest distance from vertex i to vertex j. Initialize this matrix as follows:
   • Set dist[i][j] = 0 if i == j
   • Set dist[i][j] = weight of edge (i, j) if there is an edge from i to j.
   • Set dist[i][j] = ∞ (infinity) if there is no edge from i to j.

/**
 * Floyd-Warshall Algorithm to find the shortest paths between all pairs of nodes.
 * @param {number[][]} graph - Adjacency matrix representing the graph.
 * @return {number[][]} - Distance matrix with the shortest paths.
 */
function floydWarshall(graph) {
  const V = graph.length;
  const distance = Array.from({ length: V }, (_, i) => Array.from(graph[i]));

  // Initialize distances based on input graph
  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (distance[i][k] !== Infinity && distance[k][j] !== Infinity) {
          distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
        }
      }
    }
  }

  return distance;
}

// Example usage:
const graph = [
  [0, 3, Infinity, Infinity],
  [2, 0, Infinity, 1],
  [Infinity, 7, 0, 2],
  [6, Infinity, 3, 0]
];

const shortestPaths = floydWarshall(graph);
console.log(shortestPaths); //[ [ 0, 3, 7, 4 ], [ 2, 0, 4, 1 ], [ 8, 7, 0, 2 ], [ 6, 9, 3, 0 ] ]

/* 
Time Complexity: O(V^3)
Space Complexity: O(V^2)
*/