Floyd-Warshall Algorithm: All-Pairs Shortest Paths

1. From Single-Source to All-Pairs Shortest Path

The problem we're tackling now is finding the shortest path from every node to every other node in the graph. As we discussed, you could run Bellman-Ford V times, once for each starting vertex. This would have a time complexity of V * O(V*E), which is O(V^2 * E). For a dense graph where E is approximately V^2, this approaches O(V^4).

The Floyd-Warshall algorithm provides a more straightforward O(V^3) solution, which is often simpler to implement and more efficient for dense graphs. It works for both directed and undirected graphs and can handle negative edge weights.

2. The Core Idea: Paths Through Intermediate Vertices

The intuition behind Floyd-Warshall is surprisingly simple. For any pair of vertices i and j, the shortest path between them is either the direct edge connecting them or a path that goes through some other intermediate vertex k.

The algorithm systematically considers every possible vertex as an intermediate point for every possible pair of source and destination vertices. It asks a simple question:

Is the path from i to j shorter if we go via vertex k?

dist(i, j) vs. dist(i, k) + dist(k, j)

We do this for every possible intermediate vertex k, and for every pair (i, j), we update dist(i, j) if we find a shorter path. This dynamic programming approach builds up the final solution by iteratively improving path estimates.

Let's watch a video that explains this core concept.

3. The Algorithm in Detail

The Floyd-Warshall algorithm uses an adjacency matrix to store the distances between vertices. This matrix is updated in place.

Step 1: Initialization

We start with a V x V distance matrix, let's call it dist.

• If there is a direct edge from i to j with weight w, dist[i][j] = w.
• The distance from a node to itself is 0, so dist[i][i] = 0.
• If there is no direct edge from i to j, we set dist[i][j] = ∞ (a very large value like Integer.MAX_VALUE).

This initial matrix represents the shortest paths using 0 intermediate vertices.

Step 2: The Main Loop

The algorithm then proceeds with three nested loops. The order of these loops is critical for the algorithm to work correctly: the outermost loop must be for the intermediate vertex k.

for k from 0 to V-1:      // Current intermediate vertex
    for i from 0 to V-1:  // Source vertex
        for j from 0 to V-1:  // Destination vertex
            // If the path from i to j through k is shorter, update it
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }

After the k-th iteration of the outer loop, the dist matrix will contain the shortest paths between all pairs of vertices, considering only the vertices {0, 1, ..., k} as possible intermediate nodes. After the final iteration (k = V-1), the matrix contains the true all-pairs shortest paths.

Let's see this matrix transformation in action.

Test your understanding!

Given the following initial distance matrix (where INF is infinity):

  0   1   2
0[0,  8, INF]
1[INF,0,  1]
2[4, INF, 0]

What will be the value of dist[0][1] after the outer loop for k = 2 completes?

Show answer

The update rule is dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Here, i=0, j=1, and k=2.
The current dist[0][1] is 8.
The new potential path is dist[0][2] + dist[2][1].
dist[0][2] is INF. dist[2][1] is INF in the initial matrix. But let's assume after k=0 and k=1, no changes were made.
When k=2, we check dist[0][1] against dist[0][2] + dist[2][1]. The initial values are dist[0][2] = INF. So no update happens.
Wait, let's trace properly.
k=0: dist[2][1] could be updated by dist[2][0] + dist[0][1] = 4+8=12. No update for dist[2][1].
k=1: No updates.
k=2: Let's check dist[0][1]. We compare dist[0][1] with dist[0][2] + dist[2][1].

• dist[0][1] is 8.
• dist[0][2] is INF. So we don't update.
  Let's check dist[1][0]. We compare dist[1][0] with dist[1][2] + dist[2][0].
• dist[1][0] is INF.
• dist[1][2] is 1.
• dist[2][0] is 4.
• 1 + 4 = 5. Since 5 < INF, dist[1][0] becomes 5.
  Let's go back to dist[0][1]. We check dist[0][1] vs dist[0][2] + dist[2][1].
• dist[0][1] is 8.
• We check dist[0][2] + dist[2][1]. dist[0][2] is INF, so no update.
  Let me rephrase the question. What will be the value of dist[0][1] after the full algorithm runs?
  The path 0 -> 2 -> 1 is not possible.
  The path 0 -> 1 is 8.
  The path 2 -> 0 -> 1 has cost 4 + 8 = 12.
  The path 1 -> 2 -> 0 has cost 1 + 4 = 5. So dist[1][0] becomes 5.
  Let's trace dist[0][1] after all k loops.
  Initially dist[0][1] = 8.
  k=0: No change to dist[0][1].
  k=1: No change to dist[0][1].
  k=2: We check dist[0][1] vs dist[0][2] + dist[2][1]. dist[0][2] is INF. No change.

It seems I misconstructed the problem. Let's try another one. What is dist[0][1] at the end?
The paths from 0 to 1 are:

1. Direct: 0 -> 1 (cost 8)
2. Via 2: 0 -> 2 -> 1. This path does not exist.
   The final distance is 8.

Let's re-think the question to be more illustrative.
What will be dist[2][1] at the end of the algorithm?
Initial dist[2][1] is INF.
k=0: we check dist[2][1] vs dist[2][0] + dist[0][1]. 4 + 8 = 12. So dist[2][1] becomes 12.
k=1: no change.
k=2: no change.
Final dist[2][1] is 12.

Let's use this for the exercise.

Test your understanding!

Given the following initial distance matrix (where INF is infinity):

  0   1   2
0[0,  3, INF]
1[2,  0,  -2]
2[INF, 7,  0]

What will be the final value of dist[0][2] after the algorithm completes?

Show answer

The final value will be 1. Let's trace it:

• The initial value of dist[0][2] is INF.
• When k=0, we check dist[0][2] vs dist[0][0] + dist[0][2]. No change.
• When k=1, we check dist[0][2] vs dist[0][1] + dist[1][2].
  • dist[0][1] is 3.
  • dist[1][2] is -2.
  • 3 + (-2) = 1.
  • Since 1 < INF, we update dist[0][2] to 1.
• When k=2, we check dist[0][2] vs dist[0][2] + dist[2][2]. No change.
  The final shortest path from 0 to 2 is via vertex 1, with a cost of 1.

4. Java Implementation

Let's translate the algorithm into Java code. A key detail is handling infinity. We use a large integer, but we must be careful to avoid overflow when adding two "infinite" values. A common practice is to use Integer.MAX_VALUE / 2 to prevent INF + INF from wrapping around to a negative number.

Floyd Warshall Algorithm

The article 'Floyd Warshall Algorithm' from Programiz provides a very clean and straightforward Java implementation that directly follows the logic we've discussed.

Please study the Java code example provided in this article. Note how the initial matrix is created as a copy of the input graph and then updated in place. The three nested loops are implemented exactly as described in the pseudocode.

5. Detecting Negative Cycles

Like Bellman-Ford, Floyd-Warshall can also detect negative cycles. The method is elegant:

After the algorithm has finished, if the distance from any vertex i to itself (dist[i][i]) is a negative number, then the graph contains a negative cycle.

Normally, dist[i][i] is always 0. However, if vertex i is part of or can reach a negative cycle, the algorithm will continuously try to shorten the path by looping through that cycle, eventually resulting in a negative value for the path from i back to itself.

Let's watch a quick explanation of this detection mechanism.

G-42. Floyd Warshall Algorithm

The 'take U forward' video concludes with a clear explanation of how to detect negative cycles.

Watch the segment from 22:38 to 24:35. The key takeaway is the simple condition dist[i][i] < 0 to check for negative cycles after the main loops have completed.

6. Complexity Analysis

The complexity analysis for Floyd-Warshall is very direct.

• Time Complexity: The algorithm is dominated by the three nested loops, each running from 0 to V-1. This gives a time complexity of O(V³).

• Space Complexity: We need to store the V x V distance matrix. This results in a space complexity of O(V²).

For interview purposes, it's important to remember these complexities and to know when Floyd-Warshall is a good choice (dense graphs, all-pairs requirement) versus when single-source algorithms like Dijkstra's or Bellman-Ford are more appropriate.

Conclusion

Congratulations! You've learned the Floyd-Warshall algorithm, a powerful tool for solving the all-pairs shortest path problem. Its simple structure and dynamic programming foundation make it a classic and important algorithm.

Key Takeaways:

• Floyd-Warshall solves the all-pairs shortest path problem.
• It's a dynamic programming algorithm that iteratively considers every vertex as an intermediate point in a path.
• The implementation uses an adjacency matrix and a triple-nested loop (k, i, j).
• It handles negative edge weights and can detect negative cycles by checking if dist[i][i] < 0 for any vertex i.
• The time complexity is O(V³) and space complexity is O(V²).

Preview of the Next Module:
The Floyd-Warshall algorithm served as a perfect, practical introduction to the power of dynamic programming. In our next module, we will dive deep into Dynamic Programming (DP) as a general problem-solving technique. We will start by learning how to optimize recursive solutions with memoization and then see how to convert them into iterative, bottom-up solutions using tabulation, starting with the classic Fibonacci problem.