☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Floyd warshall algorithm

Hard TUF ID 522 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed weighted graph with n vertices as an n × n adjacency matrix. matrix[i][j] is the weight of the edge from i to j, or -1 if there is no such edge, and matrix[i][i] = 0. Overwrite the matrix in place so that matrix[i][j] becomes the length of the shortest path from i to j, keeping -1 where j is unreachable from i.

Constraints (GeeksforGeeks “Floyd Warshall”): 1 ≤ n ≤ 100, edge weights 0 ≤ w ≤ 1000 (the -1 marker means weights are non-negative in this format).

Example 1

matrix = [[0, 1, 43],
          [1, 0, 6],
          [-1, -1, 0]]
answer = [[0, 1, 7],      // 0 -> 1 -> 2 costs 1 + 6 = 7, cheaper than the direct 43
          [1, 0, 6],
          [-1, -1, 0]]    // vertex 2 has no outgoing edges

Example 2

matrix = [[0, 25], [-1, 0]]
answer = [[0, 25], [-1, 0]]   // nothing to improve; 1 cannot reach 0

This is the all-pairs shortest path problem: one answer for every ordered pair of vertices, rather than distances from a single source.

Approach 1: Brute force, a single-source algorithm from every vertex

Intuition. We already know how to get distances from one source. Run that algorithm once per vertex and fill in one row of the answer each time. Bellman-Ford is the most general choice, since it also tolerates negative weights. On a matrix, one round of Bellman-Ford relaxes all n² matrix entries, and it needs n - 1 rounds.

The answers must be computed from the original edge weights, so we collect all rows in a separate array and only overwrite the input at the end.

Algorithm.

  1. For every source src: set dist[src] = 0 and everything else to infinity.
  2. Repeat n - 1 times: for every pair (u, v) with an edge, relax dist[v] through u.
  3. Store dist as row src of the result.
  4. Copy the result into matrix, writing -1 for infinity.
static void bruteForce(int[][] matrix) {
    int n = matrix.length;
    int[][] result = new int[n][];
    for (int src = 0; src < n; src++) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 1; round < n; round++) {
            for (int u = 0; u < n; u++) {
                if (dist[u] == INF) continue;
                for (int v = 0; v < n; v++) {
                    if (matrix[u][v] != -1 && dist[u] + matrix[u][v] < dist[v]) dist[v] = dist[u] + matrix[u][v];
                }
            }
        }
        result[src] = dist;                          // keep the input intact until every source is done
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) matrix[i][j] = result[i][j] == INF ? -1 : result[i][j];
    }
}

Complexity. Time O(n^4): n sources × (n - 1) rounds × n² entries. For n = 100 that is 10^8 steps, borderline. Space O(n²) for the result.

With non-negative weights, Dijkstra from every vertex gives O(n · E log n), which is better on sparse graphs. On a dense matrix (E ≈ n²) it is O(n³ log n), still worse than what follows, and it breaks with negative edges.

Approach 2: Optimal, Floyd-Warshall

Intuition. Floyd-Warshall builds the answer by gradually allowing more vertices to be used as intermediate stops. Define d_k[i][j] as the shortest path from i to j whose intermediate vertices all come from {0, 1, …, k - 1}. With k = 0 no intermediates are allowed, so d_0 is just the input matrix. Going from k to k + 1 we may also pass through vertex k. A shortest path with intermediates in {0..k} either avoids k, in which case it costs d_k[i][j], or visits k exactly once, splitting into i → k and k → j, each using only {0..k-1}. So:

d_(k+1)[i][j] = min(d_k[i][j], d_k[i][k] + d_k[k][j])

After all n vertices have been allowed, d_n[i][j] is the true shortest distance.

Why can it all happen in one matrix, overwritten in place? During phase k, row k and column k do not change: d[i][k] would become min(d[i][k], d[i][k] + d[k][k]), and d[k][k] = 0 (assuming no negative cycle). So the values we read from row and column k are the same old values the formula asks for.

Algorithm.

  1. Replace every -1 with a large INF.
  2. For via = 0..n-1, for every i, for every j: if d[i][via] and d[via][j] are finite and their sum beats d[i][j], store the sum.
  3. Turn every remaining INF back into -1.
static void floydWarshall(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) if (matrix[i][j] == -1) matrix[i][j] = INF;
    }
    for (int via = 0; via < n; via++) {
        for (int i = 0; i < n; i++) {
            if (matrix[i][via] == INF) continue;     // i cannot reach via, nothing to improve
            for (int j = 0; j < n; j++) {
                if (matrix[via][j] != INF && matrix[i][via] + matrix[via][j] < matrix[i][j]) {
                    matrix[i][j] = matrix[i][via] + matrix[via][j];
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) if (matrix[i][j] == INF) matrix[i][j] = -1;
    }
}

The via loop must be the outermost loop. Swapping it inside the i or j loop gives code that looks similar but computes wrong answers, because a pair would be finalised before all intermediates had been allowed.

Dry run on Example 1 (INF written as ∞):

phase change matrix after
start   [[0,1,43],[1,0,6],[∞,∞,0]]
via = 0 d[1][2]: 1 + 43 = 44 > 6, no change same
via = 1 d[0][2]: 1 + 6 = 7 < 43 [[0,1,7],[1,0,6],[∞,∞,0]]
via = 2 row 2 is all ∞ except d[2][2], nothing to add same

Complexity. Time O(n³): three nested loops of n. Space O(1) extra, since the matrix is updated in place. For n = 100 that is 10^6 steps.

Negative weights and negative cycles

The GeeksforGeeks format uses -1 as “no edge”, so it cannot express negative weights. With a proper INF sentinel, Floyd-Warshall handles negative edges unchanged, and it detects negative cycles for free. If vertex i lies on a negative cycle, the path i → … → i around it is shorter than 0, so after the algorithm d[i][i] < 0. Checking the diagonal is enough.

static boolean hasNegativeCycle(int n, int[][] edges) {
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] e : edges) dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
    for (int via = 0; via < n; via++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][via] != INF && dist[via][j] != INF && dist[i][via] + dist[via][j] < dist[i][j]) {
                    dist[i][j] = dist[i][via] + dist[via][j];
                }
            }
        }
    }
    for (int i = 0; i < n; i++) if (dist[i][i] < 0) return true;
    return false;
}

Two cautions. When negative cycles exist, distances on and beyond them are meaningless, and repeated additions can push values far below zero, so use long on large inputs. And the in-place argument above relied on d[k][k] = 0; with a negative cycle it no longer holds, which is fine because the distances are undefined anyway.

Edge cases and pitfalls