Floyd Warshall algorithm

Floyd-Warshall efficiently finds the shortest paths between all pairs of vertices in a graph. Handles graphs with negative edge weights, but it cannot detect negative cycles.

Hint

Initialization:

• Create a 2D array dist to store the shortest distances between all pairs of vertices.
• Initialize dist with the given graph's edge weights. If there's no direct edge between two vertices, initialize their distance as Infinity.

Floyd-Warshall Algorithm:

• Iterate through all possible intermediate vertices (k).
• For each pair of vertices (i, j), check if the distance from i to j can be shortened by going through the intermediate vertex k.
• If dist[i][k] + dist[k][j] is less than the current dist[i][j], update dist[i][j] with the shorter distance.

Result:

• After the algorithm completes, the dist array will contain the shortest distances between all pairs of vertices in the graph.

• Python
• Javascript
•  Run

def floydWarshall(graph):
  V = len(graph)
  dist = [[float('inf') for _ in range(V)] for _ in range(V)]
  
  for i in range(0, V):
    for j in range(0, V):
      dist[i][j] = float('inf') if graph[i][j] == float('inf') else graph[i][j]

  for k in range(0, V):
    for i in range(0, V):
      for j in range(0, V):
        if dist[i][k] != float('inf') and dist[k][j] != float('inf') and dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  return dist

graph = [
  [0, 5, float('inf'), 10],
  [float('inf'), 0, 3, float('inf')],
  [float('inf'), float('inf'), 0, 1],
  [float('inf'), float('inf'), float('inf'), 0]
]

print(floydWarshall(graph))

function floydWarshall(graph) {
  const V = graph.length;
  const dist = [];
  
  for (let i = 0; i < V; i++) {
    dist[i] = [];
    for (let j = 0; j < V; j++) {
      dist[i][j] = graph[i][j] === Infinity ? Infinity : graph[i][j]; 
    }
  }

  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity && dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

const graph = [
  [0, 5, Infinity, 10],
  [Infinity, 0, 3, Infinity],
  [Infinity, Infinity, 0, 1],
  [Infinity, Infinity, Infinity, 0]
];

console.log(floydWarshall(graph));