TheAlgorithms/Go · error

negative weight cycle present

Error message

negative weight cycle present

What it means

After V iterations of Bellman-Ford relaxation, a further relaxation still shortens a distance, proving the graph contains a negative-weight cycle. BellmanFord returns (false, -1, err) because shortest paths are undefined in such a graph.

Source

Thrown at graph/bellmanford.go:45

	for n := 0; n < g.vertices; n++ {

		// Looping over all edges
		for u, adjacents := range g.edges {
			for v, weightUV := range adjacents {

				// If new shorter distance is found, update distance value (relaxation step)
				if newDistance := distances[u] + float64(weightUV); distances[v] > newDistance {
					distances[v] = newDistance
				}
			}
		}
	}

	// Check for negative weight cycle
	for u, adjacents := range g.edges {
		for v, weightUV := range adjacents {
			if newDistance := distances[u] + float64(weightUV); distances[v] > newDistance {
				return false, -1, errors.New("negative weight cycle present")
			}
		}
	}

	return distances[end] != INF, int(distances[end]), nil
}

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. Remove or rewrite edges creating the negative cycle if the model allows
2. Detect and report the offending cycle (e.g. via Bellman-Ford predecessor tracking) before computing paths
3. Use an algorithm supporting negative cycles (e.g. cycle-cancellation for min-cost flow) if such graphs are legitimate input

When it happens

Trigger: Thrown at graph/bellmanford.go:45 when the library encounters an invalid state.

Common situations: See trigger scenarios.

AI-assisted analysis of TheAlgorithms/Go@5ba447ec5f (2026-09-02). Data as JSON: /api/errors/16debc70a909f997. Report an issue: GitHub.