Floyd-Warshall is designed to solve the all pairs shortest path problem. This is the SSSP solved n times. Using Bellman-Ford, this would take $O(n^4)$ time on sparse graphs. Thus, we need a more efficient approach.

Outline

• Input: A weighted directed graph with (n) vertices.
• Goal: Compute shortest paths between all pairs of vertices.
• Key idea: We create subproblems by limiting the number of vertices we are allowed to look at. This allows us to do the processing of each sub-problem in constant time.

Defining subproblems

Define $D^{(k)}[i][j]$: the shortest path distance from vertex (i) to vertex (j) using only intermediate vertices from the set ${1, 2, \dots, k}$.

Base case

$D^{(0)}[i][j] = w(i, j)$ where $w(i, j)$ is the direct edge weight (or $\infty$ if no edge exists).

Recursive Step

$D^{(k)}[i][j]= \min (D^{(k-1)}[i][j], D^{(k-1)}[i][k] + D^{(k-1)}[i][k])$

Here is how this may be implemented:

procedure FloydWarshall(Graph):
    // Let Graph be represented as adjacency matrix dist[][]
    // dist[i][j] = weight of edge (i, j), or ∞ if no edge

    n = number of vertices in Graph

    // Initialize distance matrix (Handle Base Cases)
    for i from 1 to n:
        for j from 1 to n:
            if i == j:
                dist[i][j] = 0
            else if edge(i, j) exists:
                dist[i][j] = weight(i, j)
            else:
                dist[i][j] = ∞

    // Main triple loop (Recursive Steps)
    for k from 1 to n:                // intermediate vertex
        for i from 1 to n:            // source vertex
            for j from 1 to n:        // destination vertex
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

Complexity

• Time: $O(n^3)$ (triple nested loop over $k, i, j$).

  Reasoning in a different way, there are $O(n^3)$ states and each state takes $O(1)$ time to compute.

• Space: $O(n^2)$ (distance matrix).

Whether it is possible to come up with an algorithm for the all pairs shortest path problem that works in less than $O(n^3)$ time is an open problem.

Example Problems

All-pairs reachability problem

Given a directed graph, return a matrix M such that M [u][v] = 1 if u can reach v, 0 otherwise. Floyd-Warshall leads to the classic $O(V^3)$ approach, where you repeatedly update reachability using an intermediate-vertex recurrence. It is easy to implement and works well for dense graphs conceptually, but it is cubic time.

However, there is a faster approach to this problem using matrices.