TheAlgorithms/C-Sharp · error · InvalidOperationException

Graph contains a negative weight cycle.

Error message

Graph contains a negative weight cycle.

What it means

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.

Solutions

1. Find and remove the negative-weight cycle, or correct erroneous negative edge weights in the graph data.
2. 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.
3. 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.
4. Switch to an algorithm that tolerates negative cycles (reporting affected nodes) if your use case requires partial results.

Example fix

// before
try { distances = BellmanFord.ShortestPath(graph, source); }
catch (InvalidOperationException) { /* unhandled */ }

// after
try
{
    distances = BellmanFord.ShortestPath(graph, source);
}
catch (InvalidOperationException ex) when (ex.Message.Contains("negative weight cycle"))
{
    logger.LogWarning("Graph unusable for shortest path: {Reason}", ex.Message);
    return ArbitrageOpportunityDetected; // handle as domain result
}

// Cannot be cheaply pre-validated; Bellman-Ford itself is the detector.
// If your domain forbids negative weights, validate input edges:
if (edges.Any(e => e.Weight < 0))
    logger.LogWarning("Graph has negative edge weights; negative cycles are possible.");

try
{
    var dist = BellmanFord.ShortestPath(graph, source);
}
catch (InvalidOperationException ex) when (ex.Message.Contains("negative weight cycle"))
{
    // No finite shortest path exists; handle as domain outcome (e.g. arbitrage found)
}

When it happens

Trigger: 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).

Common situations: 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.

Understand the failure class

Background: "Invalid state transition" errors: "status must be X, actually Y", "already rejected/charging/uninstalled", "cannot ... while running" — what they mean when a library rejects your call — this error's family across 31 libraries.

Related errors

• Matrix must be symmetric!
• Graph must be undirected!
• Adjacency matrix must be square!
• Adjacency matrix must be symmetric!
• Graph must be connected!

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/5a854f7dbe2fde32. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/Graph/BellmanFord.cs:106

            }
        }
    }

    private void CheckForNegativeCyclesForVertex(Vertex<T> u)
    {
        foreach (var neighbor in graph.GetNeighbors(u))
        {
            if (neighbor == null)
            {
                continue;
            }

            var v = neighbor;
            var weight = graph.AdjacentDistance(u, v);

            if (distances[u] + weight < distances[v])
            {
                throw new InvalidOperationException("Graph contains a negative weight cycle.");
            }
        }
    }
}

View on GitHub (pinned to 96e2905cab)