Negative Weights: Bellman-Ford, Negative Cycle Reconstruction & Systems of Difference Constraints

The Path-Relaxation Property & Negative Cycle Witness

Let a shortest simple path from $s$ to $v$ be $P = \langle v_0, v_1, \dots, v_k \rangle$ where $v_0 = s$, $v_k = v$, and $k \le |V| - 1$.

1. Reconstructing the Exact Negative Cycle

Notice a subtle trap: if vertex $v$ is relaxed on pass $V$, $v$ might not lie on the negative cycle itself—it might merely be a downstream vertex reachable from a negative cycle $C$. However, because the predecessor subgraph traced backward from $v$ has out-degree $1$ in the reversed sense and was updated within the last $V$ steps, executing for (int i = 0; i < V; ++i) x = parent[x]; walks backward out of the downstream tail and is guaranteed to place $x$ on the cycle $C$. From there, following $\text{parent}$ until returning to $x$ extracts the exact cycle.

2. Systems of Difference Constraints ($x_v - x_u \le w$)

Suppose a scheduling or VLSI layout problem gives $M$ linear inequalities of the form:

Compare this directly with the shortest-path triangle inequality $\delta(s, v) \le \delta(s, u) + w(u, v)$! By creating a directed edge $(u, v)$ of weight $w_{u,v}$ for each constraint $x_v - x_u \le w_{u,v}$ and adding a virtual source $s^*$ with $0$-weight edges to all variables, the system of inequalities has a feasible solution if and only if the constraint graph has no negative cycle, and setting $x_v = \delta(s^*, v)$ is a valid solution!

Complexity Matrix

Production Implementation: Bellman-Ford with Exact Negative Cycle Reconstruction

#include <vector>
#include <algorithm>

struct BFEdge {
    int u, v;
    long long weight;
};

// Finds any negative cycle in the graph (initializing dist to 0 acts as a virtual super-source!)
std::vector<int> findNegativeCycle(int n, const std::vector<BFEdge>& edges) {
    std::vector<long long> dist(n, 0);
    std::vector<int> parent(n, -1);
    int lastRelaxed = -1;

    for (int step = 0; step < n; ++step) {
        lastRelaxed = -1;
        for (const auto& e : edges) {
            if (dist[e.u] + e.weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.weight;
                parent[e.v] = e.u;
                lastRelaxed = e.v;
            }
        }
        if (lastRelaxed == -1) return {}; // Early exit: no negative cycle exists
    }

    // Walk backward n steps to guarantee landing strictly inside the negative cycle
    int cycleNode = lastRelaxed;
    for (int i = 0; i < n; ++i) {
        cycleNode = parent[cycleNode];
    }

    std::vector<int> cycle;
    for (int cur = cycleNode;; cur = parent[cur]) {
        cycle.push_back(cur);
        if (cur == cycleNode && cycle.size() > 1) break;
    }
    std::reverse(cycle.begin(), cycle.end());
    return cycle;
}