Floyd-Warshall Algorithm (Multi-Source Shortest Path)

The Floyd-Warshall Algorithm is a classic dynamic programming algorithm designed to find the shortest paths between all pairs of vertices in a weighted, directed graph. Unlike Dijkstra's or Bellman-Ford algorithms—which are single-source shortest path algorithms—Floyd-Warshall computes the shortest distance from every node to every other node in a single execution.

1. Why Do We Need This? (Problem Statement & Status Quo)

• Single-Source Limitation: Algorithms like Dijkstra and Bellman-Ford take a single source node ($u$) and compute shortest paths to all other nodes ($v$). If you need distances between all pairs of nodes, running Dijkstra from every single node is inefficient or breaks down in the presence of negative edge weights.
• Multi-Source Requirement: In routing, network analysis, or transit planning, we often need an all-pairs shortest path matrix.
• Negative Edge Weights: Unlike Dijkstra, Floyd-Warshall handles graphs with negative edge weights.
• Negative Cycle Detection: It can successfully detect the presence of negative weight cycles in a graph.

2. Core Mental Model & Analogy

Real-Life Analogy: The Transit Hub Stopover

Imagine traveling across cities. To find the shortest path from City $A$ to City $B$, you can either drive directly, or you can check if stopping over at an intermediate City $K$ makes the trip shorter. If you systematically test every city in the country as a potential intermediate stopover ($K$) for every pair of starting ($I$) and ending ($J$) cities, you will eventually discover the absolute shortest routes possible.

3. Naive vs. Better Approach

• Naive Approach (Running Dijkstra $V$ times):
  • Run Dijkstra from every node $0$ to $V-1$.
  • Time Complexity: $O(V \cdot (V + E \log V))$ or $O(V^2 \log V + V \cdot E)$.
  • Limitation: Dijkstra fails or results in Time Limit Exceeded (TLE) / infinite loops if the graph contains negative weight edges or negative cycles.
• Better Approach (Floyd-Warshall Dynamic Programming):
  • Iteratively builds up solutions by considering whether routing through intermediate vertex $k$ improves the shortest path between $i$ and $j$.
  • Time Complexity: Strict $O(V^3)$.
  • Space Complexity: $O(V^2)$ in-place adjacency matrix modification.

4. Step-by-Step Evolution of the Dynamic Programming Recurrence

To find the shortest path from node $I$ to node $J$:

1. Direct Path: $\text{Cost}(I \to J)$ without any intermediate nodes.
2. Path via Node $K$: Go from $I$ to $K$, then from $K$ to $J$.
3. Transition State Formula:

As we iterate $k$ from $0$ to $n-1$, we progressively allow more vertices to act as intermediate stopovers. By the time $k$ reaches $n-1$, all possible intermediate stopovers have been factored in.

5. Initializing the Adjacency Matrix

Instead of an adjacency list, Floyd-Warshall uses an Adjacency Matrix (or Cost Matrix) to store edge weights.

Initial Rules for Cost Matrix:
- cost[i][i] = 0 (Distance from a node to itself is always zero)
- cost[i][j] = weight (If a direct directed edge exists from i to j)
- cost[i][j] = Infinity / Very Large Number (e.g., 1e9) (If no direct edge exists)

Handling Undirected Graphs

If the graph is undirected with an edge weight $W$ between node $u$ and node $v$, split it into two directed edges:

• $u \to v$ with weight $W$
• $v \to u$ with weight $W$

6. Complete Flow Walkthrough of the Algorithm

Code Implementation (C++ and Java)

// C++ Implementation of Floyd-Warshall Algorithm
class Solution {
public:
    void shortest_distance(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        // Step 1: Preprocess - convert -1 (unreachable) to a large number (1e9)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    matrix[i][j] = 1e9;
                }
                if (i == j) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Step 2: Core Floyd-Warshall Logic -> via every vertex k
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = min(matrix[i][j], 
                                       matrix[i][k] + matrix[k][j]);
                }
            }
        }
        
        // Step 3: Postprocess - convert 1e9 back to -1 for unreachable nodes
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1e9) {
                    matrix[i][j] = -1;
                }
            }
        }
    }
};

// Java Implementation of Floyd-Warshall Algorithm
class Solution {
    public void shortestDistance(int[][] matrix) {
        int n = matrix.length;
        
        // Step 1: Preprocess - convert -1 to 1e9
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    matrix[i][j] = (int)(1e9);
                }
                if (i == j) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Step 2: Core Floyd-Warshall Logic (via k)
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = Math.min(matrix[i][j], 
                                            matrix[i][k] + matrix[k][j]);
                }
            }
        }
        
        // Step 3: Postprocess - convert 1e9 back to -1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] >= (int)(1e9)) {
                    matrix[i][j] = -1;
                }
            }
        }
    }
}

7. Negative Cycle Detection

A negative cycle is a cycle in a graph whose total sum of edge weights is negative. If you traverse a negative cycle repeatedly, the shortest path cost keeps decreasing toward negative infinity.

How to Detect Negative Cycles using Floyd-Warshall:

After running the standard algorithm, check the diagonal elements of the distance matrix (matrix[i][i]):

• Normally, the distance from a node to itself (i to i) is initialized and maintained as 0.
• If matrix[i][i] < 0 for any node i, it indicates that the path has looped through a negative cycle, reducing the cost below zero.

// Negative Cycle Detection Check
bool hasNegativeCycle = false;
for (int i = 0; i < n; i++) {
    if (matrix[i][i] < 0) {
        hasNegativeCycle = true;
        break;
    }
}
if (hasNegativeCycle) {
    cout << "Graph contains a negative weight cycle!" << endl;
}

8. Algorithm Comparison Summary

9. Summary and Key Takeaways

• Multi-Source Nature: Floyd-Warshall computes shortest paths between every pair of vertices, making it unique compared to Dijkstra and Bellman-Ford.
• Dynamic Programming Foundation: It builds solutions iteratively by checking if routing through intermediate node $k$ provides a shorter path: $\text{min}(\text{cost}[i][j], \; \text{cost}[i][k] + \text{cost}[k][j])$.
• Adjacency Matrix Requirement: The algorithm operates natively on a 2D adjacency matrix representation of the graph.
• Cubic Time Complexity: The nested loops for intermediate node $k$, source $i$, and destination $j$ result in a time complexity of $O(V^3)$.
• In-Place Space Complexity: Requires $O(V^2)$ auxiliary space (or modifies the existing cost matrix in place).
• Negative Edge Support: Safely computes shortest paths even when graphs contain negative edge weights.
• Negative Cycle Detection: A distance value of less than 0 on any diagonal entry (matrix[i][i] < 0) confirms the presence of a negative cycle.
• Interview Bonus: When discussing Floyd-Warshall in interviews, proactively explaining negative cycle detection and contrasting its performance with Dijkstra ($V \times (E \log V)$ vs $V^3$) demonstrates senior-level system and algorithmic depth.