{"record":{"id":"5a854f7dbe2fde32","repo":"TheAlgorithms/C-Sharp","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":"InvalidOperationException","httpStatus":null,"severity":"error","filePath":"Algorithms/Graph/BellmanFord.cs","lineNumber":106,"sourceCode":"            }\n        }\n    }\n\n    private void CheckForNegativeCyclesForVertex(Vertex<T> u)\n    {\n        foreach (var neighbor in graph.GetNeighbors(u))\n        {\n            if (neighbor == null)\n            {\n                continue;\n            }\n\n            var v = neighbor;\n            var weight = graph.AdjacentDistance(u, v);\n\n            if (distances[u] + weight < distances[v])\n            {\n                throw new InvalidOperationException(\"Graph contains a negative weight cycle.\");\n            }\n        }\n    }\n}\n","sourceCodeStart":88,"sourceCodeEnd":111,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/Algorithms/Graph/BellmanFord.cs#L88-L111","documentation":"CheckForNegativeCyclesForVertex in Algorithms/Graph/BellmanFord.cs throws InvalidOperationException(\"Graph contains a negative weight cycle.\") when a relaxation step still improves a distance after the main Bellman-Ford iterations — distances[u] + weight < distances[v] on a final pass (line 106). This means the shortest-path problem has no well-defined solution on this graph, so the library aborts instead of returning bogus distances.","triggerScenarios":"Running Bellman-Ford shortest path (via CheckForNegativeCycles) on any weighted directed graph containing a cycle whose total edge weight is negative — e.g. edges A->B (w=1), B->A (w=-2).","commonSituations":"Financial arbitrage detection graphs (negative weights are expected); negative edge weights entered by mistake in routing data; graphs built from user-supplied weights that were not validated; currency-exchange rate conversion graphs.","solutions":["Find and remove the negative-weight cycle, or correct erroneous negative edge weights in the graph data.","If negative cycles are legitimate (e.g. arbitrage), use this throw as the detection signal and catch InvalidOperationException to treat it as a result, not a failure.","For graphs where negative edges are needed but no cycle should exist, verify the graph structure (e.g. ensure it is a DAG) before running.","Switch to an algorithm that tolerates negative cycles (reporting affected nodes) if your use case requires partial results."],"exampleFix":"// before\ntry { distances = BellmanFord.ShortestPath(graph, source); }\ncatch (InvalidOperationException) { /* unhandled */ }\n\n// after\ntry\n{\n    distances = BellmanFord.ShortestPath(graph, source);\n}\ncatch (InvalidOperationException ex) when (ex.Message.Contains(\"negative weight cycle\"))\n{\n    logger.LogWarning(\"Graph unusable for shortest path: {Reason}\", ex.Message);\n    return ArbitrageOpportunityDetected; // handle as domain result\n}","handlingStrategy":"try-catch","validationCode":"// Cannot be cheaply pre-validated; Bellman-Ford itself is the detector.\n// If your domain forbids negative weights, validate input edges:\nif (edges.Any(e => e.Weight < 0))\n    logger.LogWarning(\"Graph has negative edge weights; negative cycles are possible.\");","typeGuard":null,"tryCatchPattern":"try\n{\n    var dist = BellmanFord.ShortestPath(graph, source);\n}\ncatch (InvalidOperationException ex) when (ex.Message.Contains(\"negative weight cycle\"))\n{\n    // No finite shortest path exists; handle as domain outcome (e.g. arbitrage found)\n}","preventionTips":["Validate or sanitize edge weights at ingestion time if your domain expects non-negative weights.","When negative weights are intentional, wrap the call and treat the exception as a detection result.","Prefer topological (DAG) shortest path when you know the graph is acyclic.","Log the graph edge list when this occurs — locating the offending cycle is the main debugging cost."],"tags":["csharp","graph","bellman-ford","negative-cycle"],"backgroundTag":"invalid-state-transition","analyzedSha":"96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c","analyzedAt":"2026-09-13T17:04:01.438Z","contentChangedAt":"2026-09-13T17:04:01.438Z","schemaVersion":2},"datasetVersion":"2026-09-16T04:17:20.429Z"}