☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Floyd Warshall Algorithm

Hard TUF ID 2829 SDE

Java source ↗ Edit this article ↗

Problem

You are given a directed weighted graph with n vertices as an n × n matrix: matrix[i][j] is the weight of the edge i → j, or -1 if there is no such edge, and matrix[i][i] = 0. Compute the shortest distance for every ordered pair (i, j). Output the result in the same format, with -1 where j cannot be reached from i. This is the sheet’s version (GFG, “Floyd Warshall”); the original updates the matrix in place, while the code here returns a new matrix so the input can be reused.

Because -1 marks a missing edge, weights in this version are non-negative. Graphs with negative weights and the negative-cycle check are covered in their own section below.

Constraints: 1 ≤ n ≤ 100, edge weights up to about 1000.

Example 1

matrix = [[0, 25], [-1, 0]]
answer = [[0, 25], [-1, 0]]                       // there is no way from 1 back to 0

Example 2

matrix = [[0, 1, 43], [1, 0, 6], [-1, -1, 0]]
answer = [[0, 1, 7], [1, 0, 6], [-1, -1, 0]]      // 0→1→2 costs 1 + 6 = 7, far below the direct 43

All approaches convert the input once, so that a missing edge becomes a large INF marker instead of -1 (which would otherwise behave like a real negative weight), and convert back at the end.

static final int INF = Integer.MAX_VALUE;                  // internal "no path" marker

/** Copies the input, turning -1 (no edge) into INF and forcing d[i][i] = 0. */
static int[][] toDist(int[][] matrix) {
    int n = matrix.length;
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) d[i][j] = i == j ? 0 : (matrix[i][j] == -1 ? INF : matrix[i][j]);
    }
    return d;
}

/** Turns INF back into -1, the output convention. */
static int[][] toAnswer(int[][] d) {
    for (int[] row : d) {
        for (int j = 0; j < row.length; j++) if (row[j] == INF) row[j] = -1;
    }
    return d;
}

Approach 1: Brute force, extend paths one edge at a time

Intuition. Let L_m[i][j] be the cheapest cost from i to j using at most m edges. L_1 is the converted matrix itself (the zero diagonal lets a path “stand still”, which is what makes it “at most”). A path with at most m + 1 edges is a path with at most m edges to some vertex k, followed by the edge k → j. So

L_(m+1)[i][j] = min over k of L_m[i][k] + W[k][j].

This is matrix multiplication with + replaced by min and × replaced by +, usually called the min-plus product. Without negative cycles, a shortest path never needs more than n - 1 edges, so L_(n-1) is the answer.

Algorithm.

  1. W = converted matrix, d = W.
  2. For m = 2 .. n - 1: d = minPlus(d, W).
  3. Convert INF back to -1.
static int[][] minPlus(int[][] a, int[][] b) {
    int n = a.length;
    int[][] out = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int best = INF;
            for (int k = 0; k < n; k++) {
                if (a[i][k] != INF && b[k][j] != INF) best = Math.min(best, a[i][k] + b[k][j]);
            }
            out[i][j] = best;
        }
    }
    return out;
}

/** Approach 1: extend shortest paths by one edge at a time until they may use n - 1 edges. O(n^4) time, O(n^2) space. */
static int[][] bruteForce(int[][] matrix) {
    int[][] w = toDist(matrix);
    int[][] d = w;                                         // d = best paths with at most 1 edge
    for (int m = 2; m <= w.length - 1; m++) d = minPlus(d, w);   // now at most m edges
    return toAnswer(d);
}

Complexity. Time O(n^4): n - 2 products of O(n^3) each. Space O(n^2). For n = 100 that is 10^8 operations, borderline in Java and needlessly slow.

Approach 2: Better, repeated squaring

Intuition. The min-plus product is associative, just like ordinary matrix multiplication. A path with at most 2m edges splits at its middle vertex into two halves of at most m edges each, so L_(2m) = L_m ⊗ L_m. Squaring repeatedly gives L_1, L_2, L_4, L_8, ..., and after ⌈log2(n - 1)⌉ squarings the allowed length is at least n - 1. Going past n - 1 is harmless: with no negative cycles, allowing more edges cannot find anything cheaper.

static int[][] better(int[][] matrix) {
    int[][] d = toDist(matrix);
    for (int len = 1; len < d.length - 1; len *= 2) d = minPlus(d, d);
    return toAnswer(d);
}

Complexity. Time O(n^3 log n), space O(n^2). For n = 100 this is about 7 × 10^6 operations. Much better, but the log n factor can be removed with a different way of growing the paths.

Approach 3: Optimal, Floyd-Warshall

Intuition. Instead of growing the number of edges a path may use, grow the set of vertices allowed as intermediate stops. Let D_k[i][j] be the cheapest path from i to j whose intermediate vertices all come from {0, 1, ..., k}. When vertex k becomes available, the best path either:

Take the smaller one. After k = n - 1, every vertex is allowed, so the matrix holds the true distances.

Updating a single matrix in place is safe. During round 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. So reading a value that was already updated in the same round gives the same number as reading the old one.

Algorithm.

  1. d = converted matrix.
  2. For k = 0 .. n - 1 (outermost!), for every i that can reach k, for every j reachable from k: d[i][j] = min(d[i][j], d[i][k] + d[k][j]).
  3. Convert back and return.
static int[][] floydWarshall(int[][] matrix) {
    int[][] d = toDist(matrix);
    int n = d.length;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (d[i][k] == INF) continue;                  // i cannot reach k, so k cannot help i
            for (int j = 0; j < n; j++) {
                if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
    return toAnswer(d);
}

Dry run on Example 2:

k Update Matrix after the round
start none [[0, 1, 43], [1, 0, 6], [∞, ∞, 0]]
0 via 0: 1→2 would cost 1 + 43 = 44 > 6, no change unchanged
1 via 1: 0→2 costs 1 + 6 = 7 < 43 [[0, 1, 7], [1, 0, 6], [∞, ∞, 0]]
2 vertex 2 reaches nothing, no change unchanged

Complexity. Time O(n^3): three nested loops of n. Space O(n^2). For n = 100, one million steps.

Detecting negative cycles

When weights can be negative, -1 can no longer mean “no edge”, so the check below takes a list of edges {u, v, w}. Run the same triple loop with d[i][i] = 0 at the start. Without negative cycles every d[i][i] stays 0, because no closed walk costs less than staying put. With one, d[i][i] < 0 for every vertex i on the cycle: the cycle is itself a closed walk from i to i, and once its highest-numbered vertex is allowed as an intermediate, the update finds a cost no larger than the cycle’s weight. The values are stored as long, because on graphs with negative cycles the entries keep shrinking during the run and could overflow an int.

static boolean hasNegativeCycle(int n, int[][] edges) {
    long[][] d = new long[n][n];
    for (long[] row : d) Arrays.fill(row, Long.MAX_VALUE);
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (d[i][k] == Long.MAX_VALUE) continue;
            for (int j = 0; j < n; j++) {
                if (d[k][j] != Long.MAX_VALUE) d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (int i = 0; i < n; i++) if (d[i][i] < 0) return true;   // a walk from i back to i with negative cost
    return false;
}

Edge cases and pitfalls