Java Floyd Warshall All Pairs Shortest Path

Introduction

The java floyd warshall algorithm computes the shortest path between every pair of vertices in a weighted graph in O(V cubed) time. It was published by Robert W. Floyd in 1962 in the Communications of the ACM paper "Algorithm 97: Shortest Path", and independently by Stephen Warshall in 1962 in the Journal of the ACM paper "A Theorem on Boolean Matrices" for the transitive closure problem. The algorithm is also sometimes credited to Peter Ingerman, who published a variant in 1962 in the Communications of the ACM. The dynamic programming formulation is clean enough to fit in three nested loops and is a standard teaching example in algorithms courses.

For a Java learner, the java floyd warshall algorithm is the simplest all pairs shortest path code you will ever write: three nested for loops, one update statement, and a small adjacency matrix. The O(V cubed) cost is steep for large graphs, but for dense graphs with V under a few hundred, Floyd Warshall is faster than running Dijkstra V times, because Dijkstra with a binary heap on a dense graph is also O(V cubed log V) and the constant factors of the heap matter. Floyd Warshall also handles negative edges, as long as there is no negative cycle.

What is Floyd Warshall?

Floyd Warshall is an all pairs shortest path algorithm based on dynamic programming. It belongs to the family of label correcting algorithms, like Bellman Ford, but it corrects labels for all sources simultaneously. The algorithm works on an adjacency matrix representation of the graph, where matrix[i][j] holds the weight of the edge from i to j, or infinity if no direct edge exists.

The dynamic programming insight is that the shortest path from i to j either does not pass through vertex k, in which case it is the shortest path in the subgraph without k, or it does pass through k, in which case it is the shortest path from i to k plus the shortest path from k to j. By iterating k from 0 to V minus 1 and updating every pair i, j in the order i then j, the matrix gradually incorporates paths that use vertices 0 through k as intermediate hops.

The algorithm runs in O(V cubed) time and uses O(V squared) memory, both for the distance matrix and for the optional predecessor matrix. It handles negative edge weights correctly, and a negative cycle is detected if any distance[i][i] becomes negative after the main loop, which means there is a cycle through i with negative total weight.

How Floyd Warshall Works - Step by Step

Step 1: Build the initial distance matrix. For every pair i, j, set distance[i][j] to the weight of the edge from i to j, or infinity if no direct edge exists. Set distance[i][i] to zero for every vertex, which represents the trivial path of length zero from a vertex to itself.

Step 2: Initialise the predecessor matrix. For every pair i, j with a direct edge, set predecessor[i][j] to i. For pairs without a direct edge, set it to negative one. The predecessor matrix lets us reconstruct the actual path, not just its length.

Step 3: For each intermediate vertex k from 0 to V minus 1, walk every pair i, j. If distance[i][k] plus distance[k][j] is less than distance[i][j], update distance[i][j] to distance[i][k] plus distance[k][j], and update predecessor[i][j] to predecessor[k][j]. The order of the loops must be k on the outside, then i, then j, so that when we process k, every pair i, j considers paths whose intermediate vertices are all less than k.

Step 4: After the k loop finishes, the distance matrix holds the shortest path between every pair of vertices. A negative cycle exists if any distance[i][i] is negative, because a self loop of negative length means the vertex lies on a cycle with negative total weight.

Step 5: To reconstruct the path from i to j, walk the predecessor matrix backwards. The predecessor of j on the path from i is predecessor[i][j], which we then use as the new j. Repeat until j equals i, prepending each vertex to the path. If predecessor[i][j] is negative one, no path exists.

Java Program for Floyd Warshall

public class FloydWarshallDemo {

    private static final int INF = 1_000_000_000;

    // Returns the all pairs shortest distance matrix. If a negative
    // cycle exists, throws IllegalStateException.
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] distance = new int[n][n];
        int[][] predecessor = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = graph[i][j];
                predecessor[i][j] = (i != j && graph[i][j] < INF) ? i : -1;
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (distance[i][k] + distance[k][j] < distance[i][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        predecessor[i][j] = predecessor[k][j];
                    }
                }
            }
        }

        // Negative cycle detection: any distance[i][i] < 0 means a cycle.
        for (int i = 0; i < n; i++) {
            if (distance[i][i] < 0) {
                throw new IllegalStateException(
                    "Graph contains a negative cycle through vertex " + i);
            }
        }

        printMatrix("Distance", distance);
        printMatrix("Predecessor", predecessor);
        return distance;
    }

    private static void printMatrix(String name, int[][] matrix) {
        System.out.println(name + " matrix:");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                int v = matrix[i][j];
                if (v >= INF) {
                    System.out.print("  INF");
                } else {
                    System.out.printf("%5d", v);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int INF = 1_000_000_000;
        int[][] graph = {
            {0,   3, INF,   7},
            {8,   0,   2, INF},
            {5, INF,   0,   1},
            {2, INF, INF,   0}
        };
        floydWarshall(graph);
    }
}

Code Explanation - Line by Line

The constant INF is one billion, which is large enough to act as infinity for any graph whose total path weight fits in a 32 bit int, but small enough that two INF values added together do not overflow. Using Integer.MAX_VALUE here would cause overflow when we add distance[i][k] plus distance[k][j] for two unreachable vertices, which would wrap to a negative number and pass the less than check, corrupting the result.

The method copies the input graph into a working distance matrix and builds a predecessor matrix in parallel. The predecessor of j on the path from i is i if there is a direct edge from i to j, otherwise negative one. The diagonal entries distance[i][i] are zero, which is the trivial self path, and predecessor[i][i] is negative one because there is no predecessor on a zero length path.

The triple loop is the heart of the algorithm. The outer k loop is on the outside, the i loop is in the middle, and the j loop is on the inside. This ordering ensures that when we process vertex k, the distance matrix already holds the shortest paths using only vertices 0 through k minus 1 as intermediates. The update distance[i][j] equal to distance[i][k] plus distance[k][j] then computes the shortest path using vertices 0 through k as intermediates.

The predecessor update uses the predecessor of the second half: predecessor[i][j] becomes predecessor[k][j]. This is correct because the path from i to j through k is the path from i to k followed by the path from k to j, and the last vertex before j on the combined path is the same as the last vertex before j on the path from k to j.

The negative cycle check walks the diagonal. If any distance[i][i] is negative after the main loop, vertex i lies on a negative cycle, because the shortest path from i back to i would be zero if no cycle exists. The IllegalStateException carries the offending vertex index to help the caller debug.

Sample Input and Output

Input:  4 vertex directed weighted graph as adjacency matrix:
        0   3 INF   7
        8   0   2 INF
        5 INF   0   1
        2 INF INF   0

Output:
Distance matrix:
    0    3    5    6
    5    0    2    3
    3    6    0    1
    2    5    7    0

Predecessor matrix:
   -1    0    1    2
    2   -1    1    2
    3    0   -1    2
    3    0    1   -1

The output shows that the shortest path from 0 to 3 is 6, which uses vertex 2 as an intermediate. Walking the predecessor matrix: predecessor[0][3] is 2, predecessor[0][2] is 1, predecessor[0][1] is 0, so the path is 0 then 1 then 2 then 3 with total weight 3 plus 2 plus 1 equals 6, which beats the direct edge 0 to 3 of weight 7. The shortest path from 1 to 0 is 5 via 1 then 2 then 3 then 0 with weight 2 plus 1 plus 2 equals 5.

Common Mistakes to Avoid

First, do not use Integer.MAX_VALUE as the infinity sentinel. Adding two Integer.MAX_VALUE values overflows to negative 2, which then passes the less than check and corrupts the matrix. Use a finite sentinel like one billion, which is large enough for any realistic path weight but small enough to avoid overflow when two unreachable distances are added.

Second, do not swap the loop order. The k loop must be on the outside. If you put k on the inside, you compute the shortest path using every possible single intermediate vertex, but you do not compose paths through multiple intermediates, which is the whole point of the algorithm.

Third, do not forget to check the diagonal for negative cycles. Some students think a negative cycle is just a vertex whose distance to itself becomes negative, which is correct, but they forget to actually check after the main loop. Without the check, the algorithm returns garbage distances that contain negative cycles as if they were valid shortest paths.

Fourth, do not update the predecessor matrix with i instead of predecessor[k][j]. The correct update is predecessor[k][j], because the last vertex before j on the new path from i to j through k is the last vertex before j on the path from k to j. Updating with i would point j back to i directly, which is only correct for direct edges, not for multi hop paths.

Real-World Applications

Floyd Warshall is the standard tool for transitive closure of a binary relation. The transitive closure of a graph is computed by running Floyd Warshall with the Boolean OR and AND operations in place of addition and minimum, which Warshall's 1962 paper described. Database query planners use transitive closure to expand foreign key joins and to compute recursive queries like the SQL WITH RECURSIVE clause.

In network routing, Floyd Warshall is used in small networks where the link state database fits in memory and the topology is stable. The OSPF protocol uses Dijkstra per router, but centralised software defined networking controllers like ONOS and OpenDaylight often run Floyd Warshall to compute the all pairs distance matrix once and answer queries in O(1).

In circuit timing analysis, Floyd Warshall is used to find the longest path through a directed acyclic circuit graph, which determines the critical path and the maximum clock frequency. The algorithm is run with maximum in place of minimum, which is the dual of the shortest path version. Negative cycles here correspond to combinational loops, which are illegal in synchronous circuits.

In graph theory research, Floyd Warshall is the standard baseline for benchmarking new all pairs shortest path algorithms. The recent advances in subcubic matrix multiplication algorithms like Williams 2014 and the theoretical work on min plus matrix multiplication all measure themselves against Floyd Warshall as the cubic baseline.

Conclusion

We built Floyd Warshall with three nested loops, an adjacency matrix, and a finite infinity sentinel. We learned that the k loop on the outside is the key to the dynamic programming invariant, that the predecessor update uses predecessor[k][j] not i, and that negative cycles are detected by checking the diagonal. Next, study A star search for the heuristic guided single target variant and the matrix multiplication algorithms that beat Floyd Warshall in theory on dense graphs.