Floyd-Warshall Algorithm for All-Pairs Shortest Paths

1. The All-Pairs Shortest Path Problem

Imagine you're designing a routing system for a small, dense network or calculating travel times between all cities on a map. In these scenarios, you need to know the shortest path not just from one starting point, but from any point to any other.

A straightforward way to solve this would be to run a single-source shortest path (SSSP) algorithm from each vertex. If your graph has no negative-weight edges, you could run Dijkstra's algorithm $V$ times, where $V$ is the number of vertices. For a dense graph where the number of edges $E$ is close to $V^2$, this would result in a complexity around $O(V\cdot V^2)=O(V^3)$ using a simple implementation of Dijkstra's. If there are negative edges, you would need to use Bellman-Ford, leading to a complexity of $O(V\cdot VE)=O(V^{2}E)$.

The Floyd-Warshall algorithm provides an alternative, exceptionally clear method that achieves $O(V^3)$ complexity and is particularly well-suited for graphs represented by an adjacency matrix. It elegantly handles both positive and negative edge weights (but not negative-weight cycles).

Let's start with a high-level overview of the algorithm and where it fits in the landscape of shortest path algorithms.

2. The Core Idea: Dynamic Programming with Intermediate Vertices

The brilliance of the Floyd-Warshall algorithm lies in its dynamic programming structure. Instead of building paths edge by edge, it considers which intermediate vertices a path is allowed to use.

Let's number the vertices from 1 to $V$. The algorithm proceeds in $V$ phases. In phase $k$, we calculate the shortest paths between all pairs of vertices $(i,j)$ that are allowed to use any of the vertices in the set $\{1,2,...,k\}$ as intermediate stops.

Let $d^{(k)}[i][j]$ be the length of the shortest path from vertex $i$ to vertex $j$ using only intermediate vertices from the set $\{1,2,...,k\}$.

• Base Case ($k=0$): Before we allow any intermediate vertices, the only paths available are direct edges. So, $d^{(0)}[i][j]$ is simply the weight of the edge from $i$ to $j$ if one exists, $\infty$ if there is no direct edge, and 0 if $i=j$. This is our initial adjacency matrix.

• Recursive Step: Now, to compute $d^{(k)}[i][j]$, we consider paths from $i$ to $j$ that can use intermediate vertices from $\{1,2,...,k\}$. There are two possibilities for the shortest such path:

  1. It does not use vertex $k$. In this case, the path only uses intermediate vertices from $\{1,...,k-1\}$, so its length is $d^{(k-1)}[i][j]$.
  2. It does use vertex $k$. This path can be broken into two parts: a path from $i$ to $k$ and a path from $k$ to $j$. Since both of these sub-paths can only use intermediate vertices from the set $\{1,...,k-1\}$, their combined length is $d^{(k-1)}[i][k]+d^{(k-1)}[k][j]$.

We take the minimum of these two cases. This gives us the core recurrence relation:

After $V$ phases, $d^{(V)}[i][j]$ will hold the shortest path from $i$ to $j$ using any of the graph's vertices as intermediates—which is the final answer.

The following reading offers a clear, formal description of this process.

To see this recurrence in action, let's watch a step-by-step example.

The image below shows the full evolution of the distance matrix for a 4-node graph. Notice how in each step $k$, the algorithm considers paths that go through vertex $k$ (highlighted row and column) and updates the distances (circled in red) if a shorter path is found.

3. Implementation, Complexity, and Negative Cycles

The algorithm's implementation is remarkably straightforward, consisting of three nested loops.

for (k = 0; k < V; ++k) {
    for (i = 0; i < V; ++i) {
        for (j = 0; j < V; ++j) {
            // If path through k is shorter
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

A crucial detail is that the outermost loop must be k. This ensures that when we are in phase k, the shortest paths using intermediate vertices {1, ..., k-1} have already been computed.

Space Optimization

You might notice that the recurrence $d^{(k)}[i][j]$ suggests we need a 3D array (or two 2D arrays for the current and previous states). However, the algorithm works correctly even if we update the 2D distance matrix in place. This is because, during iteration k, the values dist[i][k] and dist[k][j] are not changed. Their shortest paths, by definition, do not use k as an intermediate vertex. Therefore, we can safely use their (k-1)-state values to update dist[i][j] for the k-th state.

Complexity

• Time Complexity: $O(V^3)$ due to the three nested loops, each running $V$ times.
• Space Complexity: $O(V^2)$ to store the adjacency/distance matrix.

Handling Negative Weights and Cycles

The Floyd-Warshall algorithm correctly handles negative edge weights. However, if the graph contains a negative-weight cycle, the concept of a shortest path is ill-defined (you could traverse the cycle infinitely to get an arbitrarily small path cost).

The algorithm can be used to detect such cycles. After the algorithm has run, if the distance from any vertex to itself, dist[i][i], is negative, it implies that there is a negative-weight cycle reachable from vertex i.

This video provides a great walkthrough of the pseudocode and discusses the handling of negative cycles.

4. Reconstructing the Shortest Path

The algorithm as presented computes the lengths of the shortest paths. To reconstruct the actual paths, we need to store more information. A common technique is to use a successor matrix, next[i][j], which stores the first vertex on the shortest path from i to j.

Initially, if there's an edge from i to j, we set next[i][j] = j.

Then, inside the main loop, when we update the distance dist[i][j] because a shorter path through k is found, we also update the successor:
next[i][j] = next[i][k]

This means the first step on the path from i to j is the same as the first step on the path from i to k. By following these next pointers, we can reconstruct the full path.

The final segment of the Fiset video explains this reconstruction process.

Conclusion

In this lesson, you've learned the Floyd-Warshall algorithm, a powerful method for solving the all-pairs shortest path problem. Its clean, dynamic programming structure makes it both effective and conceptually elegant.

Key Takeaways:

• The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted directed graph.
• It has a time complexity of $O(V^3)$ and is well-suited for dense graphs represented by an adjacency matrix.
• Its core DP strategy involves iteratively relaxing path constraints by allowing an increasing set of intermediate vertices. The recurrence is $d^{(k)}[i][j]=\min (d^{(k-1)}[i][j],d^{(k-1)}[i][k]+d^{(k-1)}[k][j])$.
• The algorithm handles negative edge weights and can be used to detect the presence of negative-weight cycles by checking if dist[i][i] < 0 for any vertex i.
• An auxiliary successor matrix can be maintained to reconstruct the actual shortest paths.

Preview of the Next Lesson:
We will now synthesize concepts from our last two lessons. In the next session, we will explore how to formulate and solve Dynamic Programming problems on Directed Acyclic Graphs (DAGs). This involves processing the vertices in a topological order, which you learned about previously, to solve DP problems efficiently on graph structures.