Java Bellman–Ford: negative edges and reachable negative cycles

Last updated: 29 Sept 20264 min read

tutorial

Bellman–Ford computes single-source distances by repeatedly relaxing edges and detects a negative-weight cycle reachable from the source.

Java 8+. This is a complete program using JDK classes.

Bound the number of useful edges

Without a reachable negative cycle, a shortest route can be chosen without repeating a vertex, so it needs at most v-1 edges. Each pass permits another edge of improvement. If a full pass changes nothing, the distances have already reached a fixed point.

An additional pass checks whether another improvement remains possible. Only edges from a reachable vertex count: an unreachable negative cycle does not make distances from this source undefined.

The unreachable sentinel is not added to an edge weight. Doing that arithmetic can wrap into a plausible distance. The program also uses checked addition for finite distances and rejects invalid endpoints before running the relaxation loop.

Working program

import java.util.Arrays;
public class CreditRouteDistances {
    static final class Edge { final int from,to,weight;
        Edge(int from,int to,int weight){this.from=from;this.to=to;this.weight=weight;} }
    static long[] distances(int vertices,Edge[] edges,int source){
        if(vertices<1||source<0||source>=vertices)throw new IllegalArgumentException("Invalid source");
        for(Edge edge:edges)if(edge.from<0||edge.to<0||edge.from>=vertices||edge.to>=vertices)throw new IllegalArgumentException("Invalid edge");
        long[] result=new long[vertices];Arrays.fill(result,Long.MAX_VALUE);result[source]=0;
        for(int pass=1;pass<vertices;pass++){
            boolean changed=false;
            for(Edge edge:edges)if(result[edge.from]!=Long.MAX_VALUE){
                long candidate=Math.addExact(result[edge.from],edge.weight);
                if(candidate<result[edge.to]){result[edge.to]=candidate;changed=true;}
            }
            if(!changed)break;
        }
        for(Edge edge:edges)if(result[edge.from]!=Long.MAX_VALUE&&Math.addExact(result[edge.from],edge.weight)<result[edge.to])
            throw new IllegalStateException("Reachable negative cycle");
        return result;
    }
    public static void main(String[] args){
        Edge[] valid={new Edge(0,1,4),new Edge(0,2,7),new Edge(1,2,-2),new Edge(2,3,3)};
        System.out.println(Arrays.toString(distances(4,valid,0)));
        Edge[] cycle=Arrays.copyOf(valid,5);cycle[4]=new Edge(3,1,-6);
        try{distances(4,cycle,0);}catch(IllegalStateException rejected){System.out.println(rejected.getMessage());}
    }
}

Output

[0, 4, 2, 5]
Reachable negative cycle

Costs and boundaries

Worst-case relaxation uses O(v e) work and O(v) distance storage in addition to the input edges. This implementation reports distances and failure, not the cycle vertices or reconstructed routes. Path reconstruction needs predecessor state and a carefully defined unreachable result.

Common Mistakes

Do not add a weight to Long.MAX_VALUE.
The cycle must be reachable from this source to invalidate its distances.
Dijkstra is not a drop-in replacement when negative edges are permitted.