Java Floyd–Warshall: all-pairs distances and negative-cycle rejection

Java 8+. The program uses JDK classes and requires no preview flags.

Keep the intermediate vertex outside

The recurrence asks whether a path through the current intermediate vertex improves an existing distance. That intermediate loop is the outer loop. Reordering the loops changes which already computed paths are available and can break the recurrence.

An absent edge uses a sentinel and is never added to a finite value. A graph with negative edges can still have finite shortest paths, but a negative cycle makes some paths unbounded below. This implementation rejects the whole result when any diagonal becomes negative rather than returning a matrix with undefined entries mixed into ordinary distances.

The input matrix is copied. Parallel edges must already be reduced to their minimum direct cost, and each diagonal must represent the zero-length path. The program sets each diagonal to the smaller of zero and the supplied value so a negative self-loop is preserved for cycle detection.

Bound the model before allocating

The fixture accepts at most 200 vertices and finite edge magnitudes at most one million. That is a learning budget, not a claim that a 200-vertex matrix suits every graph. Sparse graphs with far more vertices usually need a different representation and shortest-path strategy.

Working program

import java.util.Arrays;
public class DepotAllPairs {
    static final long ABSENT=Long.MAX_VALUE;
    static long[][] distances(long[][] input){
        int n=input.length;if(n>200)throw new IllegalArgumentException("Matrix budget");
        long[][] result=new long[n][n];
        for(int i=0;i<n;i++){
            if(input[i]==null||input[i].length!=n)throw new IllegalArgumentException("Square matrix required");
            for(int j=0;j<n;j++){
                long value=input[i][j];if(value!=ABSENT&&(value<-1_000_000||value>1_000_000))throw new IllegalArgumentException("Edge budget");result[i][j]=value;
            }result[i][i]=Math.min(0,result[i][i]);
        }
        for(int via=0;via<n;via++)for(int from=0;from<n;from++)for(int to=0;to<n;to++)
            if(result[from][via]!=ABSENT&&result[via][to]!=ABSENT)result[from][to]=Math.min(result[from][to],Math.addExact(result[from][via],result[via][to]));
        for(int i=0;i<n;i++)if(result[i][i]<0)throw new IllegalStateException("Negative cycle");
        return result;
    }
    public static void main(String[] args){
        long[][] edges={{0,5,ABSENT},{ABSENT,0,-2},{ABSENT,ABSENT,0}};
        System.out.println(Arrays.toString(distances(edges)[0]));System.out.println(edges[0][2]==ABSENT);
    }
}

Output

[0, 5, 3]
true

Costs and boundaries

Time is O(V³) and matrix storage is O(V²). A negative-cycle input can amplify intermediate distances; checked addition can reject arithmetic overflow before the final cycle check. This implementation rejects such an input rather than claiming a usable finite result.

Common Mistakes

• Do not add the absent sentinel to an edge weight.
• The intermediate loop belongs outside the endpoint loops.
• A negative cycle is different from a negative edge.

Read next

Single-source negative edges, Non-negative paths.