Negative Cycles

A negative cycle is a directed cycle whose edge weights sum to less than zero. Its presence makes “shortest path” meaningless for any vertex that can reach it and be reached from it — you can loop forever and drive the cost to $-\infty$.

Detection

Bellman-Ford — $O(VE)$

Run $V-1$ relaxation rounds. Then run one more. If anything still improves, a negative cycle is reachable from the source.

bool hasNegativeCycle(int n, vector<Edge>& edges, int s) {
    vector<long long> dist(n, LLONG_MAX / 4);
    dist[s] = 0;
    for (int i = 0; i < n - 1; i++)
        for (auto& e : edges)
            if (dist[e.u] + e.w < dist[e.v]) dist[e.v] = dist[e.u] + e.w;
    for (auto& e : edges)
        if (dist[e.u] + e.w < dist[e.v]) return true;    // still improving
    return false;
}

Reachability matters

This only finds cycles reachable from s. To detect a negative cycle anywhere, initialise dist[v] = 0 for every $v$ (equivalent to a virtual source with 0-weight edges to all vertices), then run the same loop.

Extracting the cycle

Keep par[]. If round $V$ relaxes vertex $x$, walk par from $x$ exactly $V$ times to guarantee landing inside the cycle, then follow par until you return to that vertex.

int y = x;
for (int i = 0; i < n; i++) y = par[y];       // now y is on the cycle
vector<int> cyc;
for (int cur = y; ; cur = par[cur]) {
    cyc.push_back(cur);
    if (cur == y && cyc.size() > 1) break;
}
reverse(cyc.begin(), cyc.end());

Floyd-Warshall — $O(V^3)$

After the main triple loop, a negative cycle exists iff d[i][i] < 0 for some $i$. This finds cycles anywhere in the graph and identifies which vertices are on one.

for (int i = 0; i < n; i++) if (d[i][i] < 0) /* i is on a negative cycle */;

To mark every pair affected: if (d[i][k] < INF && d[k][k] < 0 && d[k][j] < INF) d[i][j] = -INF;

SPFA — $O(VE)$ worst case

Count enqueues; more than $n$ for any vertex means a negative cycle. See SPFA. Faster in practice, but hackable.

Minimum mean cycle

A related and often more useful question: find the cycle minimising the average edge weight. Karp’s algorithm does this in $O(VE)$ with a clean DP over path lengths.

${\mu }^{\ast }={\min }_{\text{cycles }C}\frac{w(C)}{|C|}={\min }_v{\max }_{0\le k<n}\frac{d_n(v)-d_k(v)}{n-k}$

Binary searching $\mu$ and testing “is there a negative cycle after subtracting $\mu$ from every edge?” is the standard alternative — and generalises to minimum cost-to-time ratio problems.

Where negative cycles are the point

Problem	Negative cycle means
Currency arbitrage (take $-\log$ of rates)	a profitable trading loop exists
Difference constraints $x_j-x_i\le c$	the system is infeasible
Min-cost flow cycle cancelling	the current flow is not yet optimal
Scheduling with relative deadlines	contradictory constraints
Game with repeatable profitable moves	unbounded score

Negative edges are fine; negative cycles are not

Bellman-Ford, Floyd-Warshall, Johnson and DAG DP all handle negative edges correctly as long as no negative cycle exists. Only Dijkstra breaks on negative edges alone — and it does so silently.

See also: Bellman-Ford · Karp’s Minimum Mean Cycle · Shortest Paths