TheAlgorithms/Java · error · IllegalArgumentException

Graph contains a negative weight cycle

Error message

Graph contains a negative weight cycle

What it means

Thrown by the Bellman-Ford phase of Johnson's algorithm when an edge can still be relaxed after V-1 passes — proof that the graph has a cycle of negative total weight. Johnson's algorithm reweights edges using Bellman-Ford shortest paths, which are undefined when a negative cycle exists, so the algorithm aborts rather than returning bogus distances.

Source

Thrown at src/main/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithm.java:115

        // Relax all edges V times
        for (int i = 0; i < numVertices; i++) {
            for (double[] edge : allEdges) {
                int u = (int) edge[0];
                int v = (int) edge[1];
                double weight = edge[2];
                if (dist[u] != INF && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // Check for negative weight cycles
        for (double[] edge : allEdges) {
            int u = (int) edge[0];
            int v = (int) edge[1];
            double weight = edge[2];
            if (dist[u] + weight < dist[v]) {
                throw new IllegalArgumentException("Graph contains a negative weight cycle");
            }
        }

        return Arrays.copyOf(dist, numVertices);
    }

    /**
     * Reweights the graph using the modified weights computed by Bellman-Ford.
     *
     * @param graph The original graph.
     * @param modifiedWeights The modified weights from Bellman-Ford.
     * @return The reweighted graph.
     */
    public static double[][] reweightGraph(double[][] graph, double[] modifiedWeights) {
        int numVertices = graph.length;
        double[][] reweightedGraph = new double[numVertices][numVertices];

        for (int i = 0; i < numVertices; i++) {

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Remove or break the negative cycle in the input graph
2. If you expected no negative weights, audit edge construction for sign errors
3. Use a different algorithm (e.g. one that detects and reports the cycle) if negative cycles are valid in your domain

Example fix

// before (negative cycle: 0->1 -5, 1->0 -5)
edges.add(new double[]{0, 1, -5});
edges.add(new double[]{1, 0, -5});
// after (correct sign)
edges.add(new double[]{0, 1, 5});
edges.add(new double[]{1, 0, 5});

// Run Bellman-Ford first; if any edge still relaxes, the graph has a
// negative cycle — do not call Johnson's algorithm on it.

try {
    JohnsonsAlgorithm.compute(graph);
} catch (IllegalArgumentException e) {
    // graph has a negative cycle; handle or report
}

When it happens

Trigger: Calling Johnson's algorithm on a graph whose edges form a cycle with negative total weight. The final relaxation check `dist[u] + weight < dist[v]` then succeeds and throws.

Common situations: Graphs derived from financial/currency arbitrage models; accidentally negated edge weights; modeling a problem with negative weights that unintentionally closes a negative cycle.

Related errors

• Source vertex is out of bounds.
• Incorrect source
• Graph contains a cycle, topological sort not possible
• Number of vertices must be positive
• Edges list must not be null or empty

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/18f69d66331c94ce. Report an issue: GitHub.