{"record":{"id":"18f69d66331c94ce","repo":"TheAlgorithms/Java","slug":"graph-contains-a-negative-weight-cycle","errorCode":null,"errorMessage":"Graph contains a negative weight cycle","messagePattern":"Graph contains a negative weight cycle","errorType":"exception","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithm.java","lineNumber":115,"sourceCode":"        // Relax all edges V times\n        for (int i = 0; i < numVertices; i++) {\n            for (double[] edge : allEdges) {\n                int u = (int) edge[0];\n                int v = (int) edge[1];\n                double weight = edge[2];\n                if (dist[u] != INF && dist[u] + weight < dist[v]) {\n                    dist[v] = dist[u] + weight;\n                }\n            }\n        }\n\n        // Check for negative weight cycles\n        for (double[] edge : allEdges) {\n            int u = (int) edge[0];\n            int v = (int) edge[1];\n            double weight = edge[2];\n            if (dist[u] + weight < dist[v]) {\n                throw new IllegalArgumentException(\"Graph contains a negative weight cycle\");\n            }\n        }\n\n        return Arrays.copyOf(dist, numVertices);\n    }\n\n    /**\n     * Reweights the graph using the modified weights computed by Bellman-Ford.\n     *\n     * @param graph The original graph.\n     * @param modifiedWeights The modified weights from Bellman-Ford.\n     * @return The reweighted graph.\n     */\n    public static double[][] reweightGraph(double[][] graph, double[] modifiedWeights) {\n        int numVertices = graph.length;\n        double[][] reweightedGraph = new double[numVertices][numVertices];\n\n        for (int i = 0; i < numVertices; i++) {","sourceCodeStart":97,"sourceCodeEnd":133,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithm.java#L97-L133","documentation":"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.","triggerScenarios":"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.","commonSituations":"Graphs derived from financial/currency arbitrage models; accidentally negated edge weights; modeling a problem with negative weights that unintentionally closes a negative cycle.","solutions":["Remove or break the negative cycle in the input graph","If you expected no negative weights, audit edge construction for sign errors","Use a different algorithm (e.g. one that detects and reports the cycle) if negative cycles are valid in your domain"],"exampleFix":"// before (negative cycle: 0->1 -5, 1->0 -5)\nedges.add(new double[]{0, 1, -5});\nedges.add(new double[]{1, 0, -5});\n// after (correct sign)\nedges.add(new double[]{0, 1, 5});\nedges.add(new double[]{1, 0, 5});","handlingStrategy":"validation","validationCode":"// Run Bellman-Ford first; if any edge still relaxes, the graph has a\n// negative cycle — do not call Johnson's algorithm on it.","typeGuard":null,"tryCatchPattern":"try {\n    JohnsonsAlgorithm.compute(graph);\n} catch (IllegalArgumentException e) {\n    // graph has a negative cycle; handle or report\n}","preventionTips":["Validate that no negative cycle exists before running Johnson's","Audit edge-weight sign conventions when modeling problems"],"tags":["graph","shortest-path","algorithm-invariant","negative-cycle"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}