Applications of Floyd-Warshall's Algorithm

We will expand on the last post on Floyd-Warshall's algorithm by detailing two simple applications. The first is using the algorithm to compute the transitive closure of a graph, the second is determining whether or not the graph has a negative cycle.

Transitive closure is simply a reachability problem (in terms of graph theory) between all pairs of vertices. So if we compute the transitive closure of a graph we can determine whether or not there is a path from vertex x to vertex y in one or more hops. Unlike the shortest path problem we aren't concerned on how long it takes to get there, only whether or not if we can eventually get there. Obviously you can simply not modify our original algorithm and assume if the distance between vertex x to vertex y is at least "infinity" then there is no way to get from vertex x to vertex y, otherwise there is a way to get there. This perfectly solves the reachability problem.

There is cleaner approach of computing the transitive closure using a slight modification of Warshall's algorithm. Instead of letting no edge between x to y be denoted by infinity, we can let it be 0 (or false). Any weighted edge is simply reduced to 1 (or true). Now instead of adding distances we use the binary-AND operation. If graph[x][k] is true and graph[k][y] is also true, then there is a way to connect x to y. Any other combination will result in failing to connect vertex x to vertex y using an intermediate node k. So graph[x][k] & graph[k][y] correctly fits our desired behaviour. As we just need 1 such intermediate node k to connect vertex x to vertex y, we combine it with the binary-OR operation as we don't care which intermediate vertex it requires to get from x to y so long as there is a path that allows us to get there.

The modified algorithm is the following:

// warshall's algorithm for transitive closure
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
         // only need one connection for it to be reachable, hence the 
         //    OR operation.
         // need both adjmat[i][k] and adjmat[k][j] to be connected for i to go 
         //    to j using intermediate node k.
         adjmat[i][j] |= (adjmat[i][k] & adjmat[k][j]);
      }
   }
}
// post-condition if adjmat[i][j] is 1 then there is a path from vertex i to j

We can make an obvious small optimisation by only running the inner loop if adjmat[i][k] is true, otherwise all the inner computations would fail anyway.

// warshall's algorithm for transitive closure - attempt 2
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      // optimise here by reducing the number of inner loops
      if (adjmat[i][k]) {
         for (int j = 1; j <= N; j++) {
            adjmat[i][j] |= (adjmat[i][k] & adjmat[k][j]);
         }
      }
   }
}
// post-condition if adjmat[i][j] is 1 then there is a path from vertex i to j

The second application is using it to detect negative cycles in a graph. How does Floyd-Warshall relate to this? Since the algorithm calculates the shortest path between all pairs of vertices we can use the "shortest path" for vertex i to itself to determine if there is a cycle. If we can reach from vertex i to itself with a cost less than 0 then we can keep looping through to successively generate shorter paths - hence the term negative cycle. Therefore it is sufficient to just check whether or not adjmat[i][i] < 0 for all vertices. This is used in many other algorithms such as the cycle-cancelling algorithm for minimum cost flows.

// warshall's algorithm for detecting negative cycles
bool cycle = false;
for (int k = 1; k <= N; k++) {
   for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
         adjmat[i][j] = min(adjmat[i][j], adjmat[i][k] + adjmat[k][j]);
      }
      if (adjmat[i][i] < 0) cycle = true;
   }
}