Floyd Warshall | Practice Medium 0 attempts
GeeksforGeeks ↗

Floyd Warshall | Practice

Medium GraphBFSDFS GeeksforGeeks

You're given a directed, weighted graph as a V x V adjacency matrix graph, where graph[i][j] holds the weight of the edge going from vertex i to vertex j, and every diagonal entry graph[i][i] is 0. Compute the shortest distance between every pair of vertices using the Floyd-Warshall all-pairs shortest path algorithm. Wherever no path connects two vertices, leave the distance at the large sentinel value 10000, which stands in for infinity.

Input Format
Implement floydWarshall(graph). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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]]

Example 2

Input
graph = [[0,10000],[10000,0]]
Output
[[0,10000],[10000,0]]

Example 3

Input
graph = [[0,10000,10000],[10000,0,-2],[10000,10000,0]]
Output
[[0,10000,10000],[10000,0,-2],[10000,10000,0]]
Constraints
  • 1 <= V <= 100
  • graph[i][i] == 0
  • 10000 denotes an absent edge; existing edge weights are integers in [-1000,1000].
  • There are no negative-weight cycles.
Test Cases (3)
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]]
Case 2
Args: [[[0,10000],[10000,0]]] Expected: [[0,10000],[10000,0]]
Case 3
Args: [[[0,10000,10000],[10000,0,-2],[10000,10000,0]]] Expected: [[0,10000,10000],[10000,0,-2],[10000,10000,0]]
Topics
GraphBFSDFS

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]).

javascript
function floydWarshall(graph) {
  const n = graph.length;
  const dist = graph.map(row => row.map(v => v === 10000 ? Infinity : v));
  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.map(row => row.map(v => v === Infinity ? 10000 : v));
}

Time Complexity: O(V³)

Space Complexity: O(V²)

Saved in this browser only. Private to you.

JavaScript