Floyd-Warshall Algorithm

Concept

Both Dijkstra and Bellman-Ford solve the Single-Source Shortest Path problem. (You provide exactly ONE starting city, and it finds the shortest paths to all other cities).

What if a company like Uber wants to calculate a massive matrix containing the absolute shortest path from EVERY city to EVERY OTHER city simultaneously?

You could just run Dijkstra’s algorithm $V$ times (once for every city).
Or, you can use the elegant Floyd-Warshall Algorithm, which solves the “All-Pairs Shortest Path” problem in 5 lines of code.

The Mechanism (Dynamic Programming)

Floyd-Warshall is fundamentally a Dynamic Programming algorithm.
It uses an $N \times N$ Adjacency Matrix initialized with the direct edge weights (and Infinity if no direct edge exists).

The algorithm loops through every single node in the graph, asking one question:
“If I use Node K as a middle-man, is the path from Node I to Node J faster than the direct path?”

For example, the direct flight from LA to NY might cost $500.
But if we check Dallas (Node K) as a middle-man, LA $\rightarrow$ Dallas is $100, and Dallas $\rightarrow$ NY is $100.
The total cost is $200! We permanently overwrite the matrix cell matrix[LA][NY] with 200.

Implementation

// Time Complexity: O(V^3) (Three nested loops)
// Space Complexity: O(V^2) (The 2D Matrix)

function floydWarshall(n: number, edges: number[][]): number[][] {
    // 1. Initialize the N x N Matrix with Infinity
    const dist = new Array(n).fill(0).map(() => new Array(n).fill(Infinity));

    // 2. The distance from a node to ITSELF is always 0
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
    }

    // 3. Load the initial direct edge weights into the matrix
    for (let [u, v, weight] of edges) {
        dist[u][v] = weight;
        // If undirected graph, also do: dist[v][u] = weight;
    }

    // 4. The Magic Triple Loop
    // K is the "Middle-Man" node we are trying to route through
    for (let k = 0; k < n; k++) {
        // I is the Source node
        for (let i = 0; i < n; i++) {
            // J is the Destination node
            for (let j = 0; j < n; j++) {
                
                // If routing I -> K -> J is faster than the current I -> J path...
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    // Overwrite it with the faster time!
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
                
            }
        }
    }

    // The matrix now perfectly contains the absolute shortest 
    // path between ANY two nodes in the entire graph.
    return dist;
}

Why it’s rarely tested

Floyd-Warshall is mathematically beautiful, but it requires $O(V^3)$ time complexity.
If a graph has 1,000 nodes, $1000^3$ is 1 Billion operations.
If a LeetCode problem has $N \le 1000$, and you try to use Floyd-Warshall, you will instantly get a Time Limit Exceeded (TLE) error.

Floyd-Warshall is only viable for incredibly tiny graphs (e.g., $N \le 200$). Because of this extreme limitation, it is very rarely the expected optimal answer in FAANG interviews, but it is excellent for impressing an interviewer as a theoretical “Did you know?” architectural discussion.

Interview Questions

Q: Can Floyd-Warshall handle Negative Weights?
A: Yes! Just like Bellman-Ford, Floyd-Warshall perfectly handles negative weights. It can also detect negative weight cycles. After the triple loop finishes, you simply check the main diagonal of the matrix (dist[i][i]). The distance from a node to itself started at 0. If dist[i][i] is ever less than 0, it mathematically proves that a negative weight cycle exists in the graph!