🧷 Floyd Warshall

This page provides introduction to Floyd Warshall Algorithm.

Overview

Floyd warshall algorithm is all pair shortest path dynamic programming algorithm.

Graph Type	Does Floyd Warshall's Algorithm Works?
Directed with positive weight edge	Yes
Directed with negative weight edge	Yes(except when graph is negative weight cycle)
Undirected with positive weight edge	Yes
Undirected with negative weight edge	Yes(except when graph is negative weight cycle)

Run Floyd Warshall

Let's apply the Floyd Warshall algorithm to the directed graph shown below to calculate the shortest distances between all pairs of nodes. The graph includes a negative weight edge, but no negative weight cycles.

The floyd warshall algorithm finds the shortest distance between all pairs of vertices by considering each vertex as an intermediate point. It runs three nested loops, two for iterating over each pair of vertices and one for selecting the intermediate vertex.

Java

public int[][] floydWarshall(int[][] dist) throws Exception {
  // loop for intermediate node 
  for(int i = 0; i < dist.length; i++) {
    // loop for from node
    for(int from = 0; from < dist.length; from++) {
      // loop for to node
      for(int to = 0; to < dist.length; to++) {
        if(dist[from][to] > dist[from][i] + dist[i][to]) {
          dist[from][to] = dist[from][i] + dist[i][to];
        }
      }
    }
  }

  for(int i = 0; i < n; i++) {
    if(dist[i][i] < 0) throw new Exception("Negative weight cycle detected");
  }
  return dist;
}

Complexity

Let's say there are $\text{N}$ nodes in a graph.

Time Complexity

Time complexity for floyd warshall algorithm is:

$$\text{O}(\text{N}^{3})$$

Space Complexity

Floyd warshell uses $\text{N} * \text{N}$ matrix for storing distance between all pairs, thereforce space complexity is:

$$\text{O}(\text{N}^{2})$$