Floyd Warshall | Practice | Problems

Given a weighted directed graph represented as an adjacency matrix graph of size V x V, find the shortest distances between every pair of vertices using the Floyd-Warshall algorithm. If no path exists, the distance remains as a large value (use 10000 to represent infinity). graph[i][j] is the weight of the edge from vertex i to vertex j. graph[i][i] is always 0.

Example:

Input: graph = [[0,3,10000,5],[2,0,10000,4],[10000,1,0,10000],[10000,10000,2,0]]
Output: [[0,3,7,5],[2,0,6,4],[3,1,0,5],[5,3,2,0]]

Sample Input

—

Sample Output

—

Constraints

1 <= V <= 100
1 <= matrix[i][j] <= 10^3 or -1

Test Cases

Case 1

Args: [[[0,3,10000,5],[2,0,10000,4],[10000,1,0,10000],[10000,10000,2,0]]] Expected: [[0,3,7,5],[2,0,6,4],[3,1,0,5],[5,3,2,0]]

Topics

Graph BFS DFS

Approach: Floyd-Warshall

Use three nested loops. For each intermediate vertex k, update the shortest path between every pair (i, j) by checking if going through k gives a shorter distance: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

function floydWarshall(graph) {
  const n = graph.length;
  const dist = graph.map(row => [...row]);
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];
  return dist;
}

Time Complexity: O(V³)

Space Complexity: O(V²)

Saved in this browser only. Private to you.