Sometimes, it might be necessary to compute the shortest paths between all pairs of vertices. For example, we might be interested in building a table of distances. One way to do that is to perform a single source shortest path for every vertex of the graph. If you use Dijkstra's algorithm for that, we end up with a runtime of O(V*(V + E)logE).

In this subsection, we shall explore an algorithm capable of solving the all pairs shortest paths problem in O(V³) time, with a remarkably simple and elegant implementation.

The algorithm uses the adjacency matrix representation and follows a dynamic programming approach. The basic idea behind it is that, when we're trying to compute the shortest-path distance between vertex i and vertex j, we try to use an intermediate vertex, k. We want to use an intermediate vertex so that doing the path from i to k and then from k to j shortens the currently computed shortest path between i and j. If we find such a vertex, then the best path we're able to compute so far between i and j must go through k. All that we need to do is, for each k, see if using it improves the shortest path between i and j, for all possible i and j.

In order to see that in practice, let's use the directed graph of Figure 6.5 that we used to illustrate Dijkstra's algorithm. The graph of Figure 6.5 has the adjacency matrix representation of the following table:

The adjacency matrix representation serves as the starting point for the Floyd-Warshall algorithm, and we iterate through it until we're left with a matrix of the weights of the shortest paths between each pair of vertices. In order to do so, let's start with vertex A, considering it as an intermediate vertex for shortest paths. Unfortunately, vertex A doesn't have inward edges, meaning that it can't be used as an intermediate vertex for shortest paths. Using vertex B, we can improve the distance from A to C (10 + 1 < ∞), and we can use it to go from A to D, but not improve the overall distance. We can also use it to improve the distance from D to C (3 + 1 < 9). Therefore, after considering B as an intermediate vertex, we're left with the distance matrix of the following table:

Now, we are going to look at vertex C. Using vertex C, we can improve the distance from A to E (11 + 4 < ∞) and B to E (1 + 4 < ∞):

Using vertex D, we can improve the distance from A to B (5 + 3 < 10), A to C (5 + 4 < 11), A to E (5 + 2 < 15), and B to E (2 + 2 < 5):

Using vertex E, we cannot improve any distance, so Table 6.9 already has the weights for the shortest paths between all pairs of vertices. Implementing the Floyd-Warshall algorithm is very simple, as the following code snippet demonstrates:

public void run() {
  for (int k = 0; k < adj.length; k++) {
    for (int i = 0; i < adj.length; i++) {
      if (adj[i][k] >= Integer.MAX_VALUE)
        continue;
      for (int j = 0; j < adj.length; j++) {
        if (adj[k][j] >= Integer.MAX_VALUE)
          continue;
        adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
      }
    }
  }
}  

Looking at the implementation, the runtime of O(V³) becomes obvious. One alternative to the Floyd-Warshall algorithm is running Dijkstra's algorithm for each vertex in the graph (so that we end up with all pairwise shortest paths). Given that its complexity is closer to multiple applications of Dijkstra's algorithm for dense graphs, the Floyd-Warshall algorithm is frequently used in practice.