Floyd-Warshall — int Overflow Causes Negative Distances

Navigation apps, network routers, ride-sharing platforms, and game AI all share one brutal requirement: they don't just need the shortest path from A to B — they need the shortest path between every pair of nodes in the graph. Dijkstra's algorithm is brilliant for single-source shortest paths, but running it once per node in a dense graph gets expensive fast. Floyd-Warshall was built for exactly this problem, and it powers real infrastructure you use every day.

The core problem Floyd-Warshall solves is called the All-Pairs Shortest Path (APSP) problem. Given a weighted graph with V vertices, find the shortest distance between every possible (source, destination) pair — including graphs with negative edge weights, as long as there are no negative-weight cycles. It achieves this through an elegant three-nested-loop dynamic programming recurrence that's deceptively simple to implement yet surprisingly deep to understand correctly.

By the end of this article you'll understand exactly why the recurrence works (not just that it does), how to implement it with proper negative-cycle detection, when Floyd-Warshall beats alternatives like repeated Dijkstra or Bellman-Ford, what the real memory and time costs look like at scale, and the production-level gotchas that will catch you out in an interview or on the job.

Why Floyd-Warshall Can Break Your Graph

Floyd-Warshall is an all-pairs shortest path algorithm that computes the shortest distances between every pair of vertices in a weighted graph. It works by iteratively considering each vertex as a potential intermediate point, updating a distance matrix with the rule: if the path through vertex k is shorter than the current known path, replace it. The algorithm runs in O(V³) time and uses O(V²) space, making it suitable for dense graphs but prohibitive for large ones.

Key properties: it handles negative edge weights but fails if the graph contains a negative cycle — in that case, distances can become arbitrarily negative. The algorithm detects negative cycles by checking if any diagonal entry in the distance matrix becomes negative after completion. In practice, Floyd-Warshall is often used in routing protocols, social network analysis, and transitive closure problems where you need all-pairs reachability.

Use Floyd-Warshall when the graph is small (V ≤ 500) and you need all-pairs distances. For larger graphs, prefer Johnson's algorithm or repeated Dijkstra. The simplicity of the triple nested loop makes it a go-to for interview questions, but its cubic runtime is a hard limit in production systems.

How Floyd-Warshall Works — Step by Step

Floyd-Warshall is a dynamic programming algorithm. Define dist[i][j] as the shortest distance from node i to node j.

Initialization: 1. Set dist[i][i] = 0 for all nodes. 2. For each edge (i, j) with weight w, set dist[i][j] = w. 3. For all other pairs, set dist[i][j] = INF (a large number).

Main loop — consider each node k as a potential intermediate stop: 4. For k from 0 to V-1: For i from 0 to V-1: For j from 0 to V-1: If dist[i][k] + dist[k][j] < dist[i][j]: Update dist[i][j] = dist[i][k] + dist[k][j]

After the triple loop, dist[i][j] holds the shortest path considering all possible intermediate nodes.

Negative cycle detection: after the main loop, if dist[i][i] < 0 for any node i, a negative cycle exists. Walking that cycle repeatedly makes costs arbitrarily small, so shortest paths are undefined.

package io.thecodeforge;

public class FloydWarshall {
    private static final long INF = Long.MAX_VALUE / 2;

    public static long[][] shortestPaths(int n, int[][] edges) {
        long[][] dist = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = (i == j) ? 0 : INF;
            }
        }
        for (int[] e : edges) {
            dist[e[0]][e[1]] = e[2]; // allow multiple edges? keep smallest
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == INF) continue;
                    long via = dist[i][k] + dist[k][j];
                    if (via < dist[i][j]) {
                        dist[i][j] = via;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) {
                return null; // negative cycle
            }
        }
        return dist;
    }
}

C++ Implementation with Overflow Guard

In C++, the default integer type is 32-bit int, and overflow when adding distances is a subtle but critical bug. Use 64-bit long long and set INF to a value that won't overflow when doubled. A common choice is LLONG_MAX / 2. The code below mirrors the Java version but with C++ syntax, including the INF guard that skips updates when either intermediate distance is INF.

This implementation also includes a safe_add that returns INF if the sum would overflow, though the guard approach already prevents overflow by not adding when either operand is INF. However, in graphs with large finite weights (e.g., 10^12), dist[i][k] + dist[k][j] could still overflow. The production-safe approach is to check before adding: if dist[i][k] > INF - dist[k][j], then the sum equals INF and should be skipped.

The template below uses std::vector<std::vector<long long>> for the matrix, which also uses dynamic allocation — important for large V.

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
using ll = long long;

const ll INF = LLONG_MAX / 2;

vector<vector<ll>> floyd_warshall(int n, const vector<vector<pair<int,ll>>>& edges) {
    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int u = 0; u < n; u++) {
        for (auto [v, w] : edges[u]) {
            dist[u][v] = min(dist[u][v], w); // handle multiple edges
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (dist[k][j] == INF) continue;
                // Check overflow before adding
                if (dist[i][k] > INF - dist[k][j]) continue;
                ll via = dist[i][k] + dist[k][j];
                if (via < dist[i][j]) {
                    dist[i][j] = via;
                }
            }
        }
    }

    // Negative cycle detection
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            // Affected node propagation can be added here
            return {}; // signal error
        }
    }
    return dist;
}

Worked Example — Tracing the Algorithm

Consider a graph with 4 nodes (0-3) and these directed edges: 0->1 weight 3, 0->3 weight 7, 1->0 weight 8, 1->2 weight 2, 2->0 weight 5, 2->3 weight 1, 3->0 weight 2

Initial dist matrix (INF = infinity): 0 1 2 3 0 [ 0, 3, INF, 7 ] 1 [ 8, 0, 2, INF] 2 [ 5, INF, 0, 1 ] 3 [ 2, INF, INF, 0 ]

After k=0 (using node 0 as intermediate): dist[1][3]: 8+7=15 < INF -> update to 15 dist[2][1]: 5+3=8 < INF -> update to 8 dist[2][3]: 5+7=12 > 1 -> no update dist[3][1]: 2+3=5 < INF -> update to 5 dist[3][2]: 2+INF -> no update

After k=1 (node 1 as intermediate): dist[0][2]: 3+2=5 < INF -> update to 5 dist[0][3]: 3+15=18> 7 -> no update dist[3][2]: 5+2=7 < INF -> update to 7

After k=2 (node 2 as intermediate): dist[0][3]: 5+1=6 < 7 -> update to 6 dist[1][3]: 2+1=3 < 15 -> update to 3 dist[3][3]: 7+1=8 > 0 -> no update

After k=3 (node 3 as intermediate): dist[0][0]: 6+2=8 > 0 -> no update dist[1][0]: 3+2=5 < 8 -> update to 5 dist[2][0]: 1+2=3 < 5 -> update to 3

Final dist matrix: 0 1 2 3 0 [ 0, 3, 5, 6 ] 1 [ 5, 0, 2, 3 ] 2 [ 3, 6, 0, 1 ] 3 [ 2, 5, 7, 0 ]

For example, shortest path 1->0 is 5 (via 1->2->3->0: weight 2+1+2=5).

Matrix Evolution: From A₀ to A₄

Each iteration of the outer loop over k produces a new distance matrix, denoted Aₖ, where Aₖ[i][j] is the shortest path from i to j that only uses intermediate nodes in {0..k-1}. The initial matrix A₀ uses no intermediate nodes (only direct edges). After k=0, A₁ considers node 0 as intermediate. After k=3, A₄ considers all nodes. Below is the evolution for the 4-node example from the worked example.

A₀ (direct edges only): [0, 3, ∞, 7] [8, 0, 2, ∞] [5, ∞, 0, 1] [2, ∞, ∞, 0]

A₁ (intermediate node 0 allowed): [0, 3, ∞, 7] [8, 0, 2, 15] [5, 8, 0, 1] (via 0: 5+3=8 for (2,1)) [2, 5, ∞, 0] (via 0: 2+3=5 for (3,1))

A₂ (intermediate nodes 0,1 allowed): [0, 3, 5, 7] (via 1: 3+2=5 for (0,2)) [8, 0, 2, 15] [5, 8, 0, 1] [2, 5, 7, 0] (via 1: 5+2=7 for (3,2))

A₃ (intermediate nodes 0,1,2 allowed): [0, 3, 5, 6] (via 2: 5+1=6 for (0,3)) [8, 0, 2, 3] (via 2: 2+1=3 for (1,3)) [5, 8, 0, 1] [2, 5, 7, 0]

A₄ (all nodes 0,1,2,3 allowed) — final: [0, 3, 5, 6] [5, 0, 2, 3] (via 3: 3+2=5 for (1,0)) [3, 6, 0, 1] (via 3: 1+2=3 for (2,0)) [2, 5, 7, 0]

Notice how each matrix builds on the previous one. The DP invariant is that after processing k, the matrix holds shortest paths using only nodes 0..k as intermediates. This phase evolution is exactly what makes Floyd-Warshall a dynamic programming algorithm.

Negative Cycle Detection and Handling

A negative weight cycle makes shortest paths undefined because you can loop infinitely to reduce cost. Floyd-Warshall can detect them easily.

After the main triple loop, check the diagonal of the distance matrix. If any dist[i][i] < 0, node i is part of a negative cycle. However, this only tells you that a cycle exists, not which nodes are affected. In fact, every node that can reach and be reached from that cycle also has undefined shortest paths (distances become -∞).

To fully identify affected nodes, run a reachability analysis: find all nodes that can reach the cycle and all nodes the cycle can reach. Those nodes' distances are effectively -∞.

In code, after detecting dist[i][i] < 0, mark node i as 'bad'. Then propagate: if dist[bad][j] < INF then j is also bad (can reach from bad). Also if dist[k][bad] < INF then k is bad (can reach bad). Combine.

INF = float('inf')

def floyd_warshall_detect_affected(n, edges):
    dist = [[INF]*n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u,v,w in edges:
        dist[u][v] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # Detect cycle nodes
    bad = [False]*n
    for i in range(n):
        if dist[i][i] < 0:
            bad[i] = True

    # Propagate: nodes that can reach or be reached from bad
    for i in range(n):
        for j in range(n):
            if dist[i][j] != INF and (bad[i] or bad[j]):
                bad[i] = bad[j] = True

    # Set affected pairs to -INF
    for i in range(n):
        for j in range(n):
            if bad[i] or bad[j]:
                dist[i][j] = -float('inf')

    return dist

Using Floyd-Warshall for Transitive Closure

Transitive closure asks: for every pair (i,j), is there a path from i to j? This is a boolean version of APSP. Floyd-Warshall can compute the transitive closure in O(V³) time by using a boolean reachability matrix instead of a distance matrix. Initialize reach[i][i] = true, and for each edge (u,v), set reach[u][v] = true. Then the core update becomes: reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j]).

This is exactly the same DP structure, but with boolean logic. It's faster to implement than a DFS/BFS from every node (O(V·(V+E))) and uses less code. However, for large graphs, you could use bitset optimisation (V³/wordsize) if the graph is dense.

One production trick: if you already have the shortest path matrix with INF, you can derive transitive closure by replacing INF with 0 and any finite distance with 1. But the dedicated boolean version saves memory and avoids overflow concerns.

public class TransitiveClosure {
    public static boolean[][] transitiveClosure(int n, boolean[][] edges) {
        boolean[][] reach = new boolean[n][n];
        for (int i = 0; i < n; i++) reach[i][i] = true;
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (edges[u][v]) reach[u][v] = true;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (reach[i][k]) {
                    for (int j = 0; j < n; j++) {
                        if (reach[k][j]) reach[i][j] = true;
                    }
                }
            }
        }
        return reach;
    }
}

When to Use Floyd-Warshall vs Alternatives

Floyd-Warshall is not always the answer. Here's when to pick it:

Use Floyd-Warshall when: - Graph is dense (E ~ V²) - V ≤ 1000 (otherwise memory becomes huge) - Negative edge weights are present (Dijkstra can't handle them) - All-pairs results are required (not just single source)

Use repeated Dijkstra when: - Graph is sparse (E << V²) - No negative edges - V is large (10k+)

Use Bellman-Ford per source when: - Negative edges exist but graph is very sparse - V ≤ 500

Use Johnson's algorithm when: - Sparse graph with negative edges and large V - It reweights via Bellman-Ford then runs Dijkstra per source

Real performance numbers: For V=1000, E=10000 (dense-ish), Floyd-Warshall is about 1 second in Java (JIT warmed). Repeated Dijkstra (binary heap) takes ~0.3 seconds. For V=5000, Floyd-Warshall takes ~100 seconds and 200 MB memory; Dijkstra takes ~2 seconds. The crossover point depends on graph density.

Advantages and Disadvantages of Floyd-Warshall

The most significant pro is simplicity: Floyd-Warshall is often the first all-pairs algorithm taught in algorithms courses. Its deterministic runtime (always V³) makes it predictable for small graphs. The biggest con is scalability — both time and memory explode with V. In production, a V=2000 graph with Floyd-Warshall takes 8 seconds (O(V³) = 8e9 operations) and 32 MB for a long matrix. V=5000 takes 125 seconds and 200 MB — already problematic. V=10000 would take 1000 seconds and 800 MB — infeasible for most real-time systems.

Handling Floating-Point Weights with EPS

When edge weights are floating-point numbers (e.g., travel time in hours), directly comparing < can produce wrong results due to tiny arithmetic errors. For example, after many updates, two paths may have distances 0.9999999 and 1.0000001 due to floating-point precision. A strict < comparison would treat the first as shorter, but the true difference is noise. The standard fix is to use an epsilon (EPS) when comparing distances. Typically, EPS = 1e-9 or 1e-12 for double-precision.

The production guard becomes: if (fabs(via - dist[i][j]) < EPS) then consider them equal and keep the existing distance to avoid oscillating updates. Or use via < dist[i][j] - EPS to consider only significant improvements. This prevents the algorithm from infinitely tightening distances due to floating-point drift.

Floating-point Floyd-Warshall is rare in competitive programming (where weights are integers), but common in real-world simulations, GIS, and physics engines. If all weights are integers, prefer integers to avoid EPS headaches entirely.

public class FloydWarshallDouble {
    private static final double INF = Double.MAX_VALUE / 2.0;
    private static final double EPS = 1e-9;

    public static double[][] shortestPaths(int n, double[][] edges) {
        double[][] dist = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = (i == j) ? 0.0 : INF;
            }
        }
        for (double[] e : edges) {
            dist[(int)e[0]][(int)e[1]] = e[2];
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == INF) continue;
                    double via = dist[i][k] + dist[k][j];
                    // Use EPS to avoid false improvements from rounding
                    if (via < dist[i][j] - EPS) {
                        dist[i][j] = via;
                    }
                }
            }
        }

        // Negative cycle detection with EPS
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < -EPS) {
                return null; // negative cycle
            }
        }
        return dist;
    }
}

Practice Problems

Solidify your understanding of Floyd-Warshall with these problems that test each aspect of the algorithm: basic implementation, negative cycle detection, transitive closure, and production-like scenarios.

1. CSES Shortest Routes II — The classic Floyd-Warshall problem: compute all-pairs shortest paths for a directed graph with positive and negative weights. Must handle up to V=500, E=2500. Validate your implementation against INF guards and negative cycle detection. [Link to CSES](https://cses.fi/problemset/task/1674)
2. Codeforces 295B: Greg and Graph — An offline version where nodes are removed one by one and you need the sum of all shortest paths after each removal. Reverse the process and build the graph by adding nodes in reverse order, applying Floyd-Warshall incrementally. Tests understanding of the DP phase property. [Link to Codeforces](https://codeforces.com/problemset/problem/295/B)
3. UVA 104: Arbitrage — Use Floyd-Warshall (or Floyd-like) to find a sequence of currency exchanges that yields a profit (positive cycle). This is a classic application of detecting positive cycles using multiplication or logarithms. [Link to UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=40)
4. SPOJ TRANSP — Transitive closure on a directed graph. Use the boolean Floyd-Warshall to determine if there is a path between every pair. Test your implementation of the OR-AND variation. [Link to SPOJ](https://www.spoj.com/problems/TRANSP/)
5. LeetCode 1462: Course Schedule IV — Equivalent to transitive closure: given prerequisites (edges), answer queries whether a course is a prerequisite of another. Use Floyd-Warshall with boolean matrix. V ≤ 100. [Link to LeetCode](https://leetcode.com/problems/course-schedule-iv/)
6. CSES Flight Routes — Given a flight network with costs, find the cheapest route between all city pairs. Must output the routes (path reconstruction) and use long to avoid overflow. [Link to CSES](https://cses.fi/problemset/task/1666)
7. Codeforces 1140C: Playlist — While not directly APSP, this problem can be solved with a variant of Floyd-Warshall to compute maximum path attribute ; practice adapting the DP pattern. [Link to Codeforces](https://codeforces.com/problemset/problem/1140/C)

Why Floyd-Warshall Actually Works — The Intuition That Saves You

Most explanations bury you in triple-nested loops and call it a day. You need to understand the invariant that makes this thing tick. Floyd-Warshall builds the shortest path by progressively relaxing constraints on which vertices are allowed as intermediate hops. At iteration k, you've computed shortest paths that only use vertices 0 through k-1 as intermediates. When you add vertex k, you ask: "Does routing through k make any existing path shorter?" That's the single line inside the loop: if (dist[i][k] + dist[k][j] < dist[i][j]).

This works because the optimal path never needs more than V-1 intermediate vertices (in a graph with no negative cycles). Each iteration adds exactly one new vertex to the allowed set. The order doesn't matter — you could permute the vertex labels and still get the same result, thanks to the beautiful property of dynamic programming on a path that's sequentially constrained. No need to worry about intermediate recomputation invalidating earlier results: the algorithm is carefully designed so that the updated dist[i][k] and dist[k][j] values are never needed incorrectly. The proof is in the loop ordering: k outermost, then i, then j. Don't mess with that order — you'll break the invariant and get garbage.

// io.thecodeforge — dsa tutorial

public class FloydWarshallWhyItWorks {
    // Runs in O(V^3) — you pay for correctness
    public static int[][] allPairsShortest(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++)
            System.arraycopy(graph[i], 0, dist[i], 0, n);
        // k MUST be outermost — this is the invariant enforcer
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == Integer.MAX_VALUE) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == Integer.MAX_VALUE) continue;
                    long candidate = (long) dist[i][k] + (long) dist[k][j];
                    if (candidate < dist[i][j]) {
                        dist[i][j] = (int) candidate;
                    }
                }
            }
        }
        return dist;
    }
}

Why Floyd-Warshall Dominates on Dense Graphs — and Fails on Sparse Ones

Every shortest-path algorithm has a niche. Floyd-Warshall is O(V^3) regardless of edge count. For a dense graph (E ~ V^2), that's optimal — you can't do better than touching each pair of vertices once. But for sparse graphs (E ~ V), running Dijkstra from every vertex gives O(V * (E log V)) = O(V^2 log V), which crushes Floyd-Warshall. Don't use a sledgehammer on a thumbtack.

Real-world dense graphs are rare: flight networks between major airports (every city to every city? Not quite), or complete graphs in genome assembly. Most graphs in practice are sparse. Social networks are sparse. Road networks are sparse. The internet topology graph is sparse. If you have a sparse graph, you want Johnson's algorithm — it beats Floyd-Warshall by leveraging fast single-source runs and handles negative edges too.

But dense graphs do appear. When you have a complete matrix of distances (like all-pairs similarity in clustering), Floyd-Warshall is your only sane option. Its simplicity also makes it the default for teaching all-pairs shortest paths — once you understand the triple loop, you understand DP on graphs. Just don't reach for it blindly.

// io.thecodeforge — dsa tutorial

public class SparseVsDenseCost {
    // Sparse graph: V=1000, E~3000 (road network)
    // Floyd-Warshall: 1e9 operations (1 sec on modern hardware? barely)
    // Dijkstra from each vertex: 1000 * (3000 log 1000) ~ 3e7 operations (30x faster)
    
    // Dense graph: V=500, E~125k (near complete)
    // Floyd-Warshall: 125e6 operations (125 million)
    // Dijkstra from each vertex: 500 * (125k log 500) ~ 62e6 operations (still slower? check constants)
    // For dense graphs, Floyd-Warshall wins due to simpler inner loop (no priority queue overhead)
    public static void main(String[] args) {
        System.out.println("For V=500, E=125k:");
        System.out.println("Floyd-Warshall O(V^3) = 125 million integer ops");
        System.out.println("Dijkstra O(V * E log V) ≈ 62 million ops + heap overhead");
        System.out.println("Floyd-Warshall often wins in practice for dense graphs.");
    }
}

Real-World Applications — Where Floyd-Warshall Pays the Bills

This algorithm isn't just a whiteboard trick. It shows up in production systems where you need answers for every pair, not just a single source. Network routing protocols (like RIP — Routing Information Protocol) used a variant of Bellman-Ford, but Floyd-Warshall's output is essentially a complete routing table. For small networks (under 1000 routers), precomputing all shortest paths with Floyd-Warshall and caching the result is simpler than running a distributed protocol.

Transportation and logistics companies use it for precomputed distance matrices between hubs. When you have 500 distribution centres, you need the shortest path between every pair — and you compute it once, store it, and query it millions of times. Floyd-Warshall gives you that matrix in one shot. No per-query Dijkstra overhead.

Another hidden gem: transitive closure in dependency graphs. If you have a system with 10,000 modules and you want to know which module depends on which (transitively), Floyd-Warshall on a boolean matrix (using bitwise OR instead of addition) solves it efficiently. Compilers use this for dead code elimination. Social networks use it for mutual friends reachability. The pattern is always the same: you need the answer for every pair, and the graph is small enough to fit in memory (or you partition it). If your graph exceeds 10,000 nodes, you probably need an approximation or a distributed approach. But for most practical dense graphs under that threshold, Floyd-Warshall is your hammer.

// io.thecodeforge — dsa tutorial

public class TransitiveClosureExample {
    // Compute reachability (transitive closure) using bitwise Floyd-Warshall
    public static boolean[][] transitiveClosure(boolean[][] graph) {
        int n = graph.length;
        boolean[][] reach = new boolean[n][n];
        for (int i = 0; i < n; i++)
            System.arraycopy(graph[i], 0, reach[i], 0, n);
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (!reach[i][k]) continue;
                for (int j = 0; j < n; j++) {
                    reach[i][j] = reach[i][j] || reach[k][j];
                }
            }
        }
        return reach;
    }
    
    public static void main(String[] args) {
        boolean[][] deps = {
            {false, true, false, false},
            {false, false, true, false},
            {false, false, false, true},
            {false, false, false, false}
        };
        boolean[][] closure = transitiveClosure(deps);
        System.out.println("Module 0 can reach module 3? " + closure[0][3]); // true
    }
}

Python and Java: Where Floyd-Warshall Actually Lives in Production

You will rarely write Floyd-Warshall from scratch in Python or Java. The algorithm is a glorified triple-nested loop. But production code demands correctness and performance. Forget C++ templates — Python and Java code dominates backend systems.

In Python, the classic nested loop runs at Python speed — meaning O(V³) is glacial above ~500 vertices. You pack your graph into a list of lists. The real trick: pre-allocate with float('inf') and skip zero-weight diagonals. Every line matters when your loop executes a hundred million times.

Java brings solid state. Use double[][] or int[][] with Integer.MAX_VALUE / 2 to avoid overflow bombs. The JVM optimizes tight loops — keep your arrays small and your indices clean. No reflection, no streams. Raw arrays beat ArrayList every time. Watch for NullPointerException on uninitialized edges. That bug cost me two hours at 3 AM.

// io.thecodeforge — dsa tutorial

public class FloydWarshallJava {
    public static final int INF = Integer.MAX_VALUE / 2;

    public static void shortestPaths(int[][] dist) {
        int n = dist.length;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] != INF) {
                        int newDist = dist[i][k] + dist[k][j];
                        if (newDist < dist[i][j]) {
                            dist[i][j] = newDist;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 3, INF, 7},
            {8, 0, 2, INF},
            {5, INF, 0, 1},
            {2, INF, INF, 0}
        };
        shortestPaths(graph);
        for (int[] row : graph) {
            System.out.println(java.util.Arrays.toString(row));
        }
    }
}

C/C++: Where You Eat The Raw Performance — Or Eat The Rust

C and C++ give you the closest thing to metal for Floyd-Warshall. No garbage collector, no runtime overhead. You own every cache miss. The standard triple loop compiles to tight SIMD-friendly code — if your graph fits in L2 cache. For a 1000-node graph (1M entries ≈ 8 MB for doubles), you're thrashing the cache. That's where real C++ devs earn their salary.

Use std::vector<std::vector<int>> for readability, but int** and manual allocation if you need max throughput. The restrict keyword in C tells the compiler pointers don't alias — that's free vectorization. Enable -O3 -march=native. Watch for signed integer overflow — it's undefined behavior in C++. Use unsigned or guard with long long.

C++ templates let you swap out types at compile time: int, float, double. But template bloat can kill icache. Profile it. Don't guess. The algorithm is just three loops — the performance comes from memory layout and compiler flags, not clever code.

// io.thecodeforge — dsa tutorial

#include <iostream>
#include <vector>
#include <limits>

const int INF = std::numeric_limits<int>::max() / 2;

void floydWarshall(std::vector<std::vector<int>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            if (dist[i][k] != INF)
                for (int j = 0; j < n; ++j)
                    if (dist[k][j] != INF) {
                        int nd = dist[i][k] + dist[k][j];
                        if (nd < dist[i][j]) dist[i][j] = nd;
                    }
}

int main() {
    std::vector<std::vector<int>> graph = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };
    floydWarshall(graph);
    for (auto& row : graph) {
        for (int val : row) std::cout << val << " ";
        std::cout << "\n";
    }
}

Pseudocode – The Bare Minimum Wiring

Most tutorials drown you in matrix doodles before you even know what the loop does. Here is the stripped logic: Floyd-Warshall is three nested loops over the same node set. The outermost loop k is the pivot — the intermediate node you allow the path to use. Inner loops i and j check if going through k beats the current best. Initialise dist[i][j] with edge weights, INF for missing edges, 0 for i==j. After the loops, dist holds all-pairs shortest paths. Why k outermost? Because each iteration lets you gradually expand the set of allowed intermediate nodes from just {0} to all nodes. If you swap loop order, you break the invariant and get wrong distances. The guard against overflow is simple: before adding, check if either operand is INF. That is the entire skeleton — everything else is syntactic sugar or memory tweaks.

// io.thecodeforge — dsa tutorial

void floydWarshall(int[][] dist, int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (dist[k][j] == INF) continue;
                int via = dist[i][k] + dist[k][j];
                if (via < dist[i][j])
                    dist[i][j] = via;
            }
        }
    }
}

Solution – Transitive Closure in One Pass

Transitive closure asks: is there any path from i to j? With Floyd-Warshall, you replace the distance matrix with a boolean reachability matrix and use logical OR/AND instead of min/add. Initialise reachable[i][j] = true if there is a direct edge or i==j, else false. Then run the same triple loop with: reachable[i][j] = reachable[i][j] | (reachable[i][k] & reachable[k][j]). Why does this work? The same gradual-expansion-of-intermediates reasoning applies — k increases the allowed detours, and OR/AND mirrors path composition. One loop nest, no arithmetic overflow, no INF sentinels. The output is an n×n boolean matrix where reachable[i][j] true means connectivity. This runs in O(n³) like the original, but uses bitsets to cut constant time drastically on dense graphs. Use it for tasks like detecting weakly connected components in directed graphs without worrying about weights.

// io.thecodeforge — dsa tutorial

boolean[][] transitiveClosure(boolean[][] reach, int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (!reach[i][k]) continue;
            for (int j = 0; j < n; j++) {
                if (reach[k][j])
                    reach[i][j] = true;
            }
        }
    }
    return reach;
}