Detecting Negative Cycles — Bellman-Ford + Reachability

Detection

boolean hasNegCycle(int V, List edges) {
  int[] dist = new int[V];
  int[] parent = new int[V];
  Arrays.fill(parent, -1);
  // Standard Bellman-Ford V-1 rounds...
  // V-th round: any improvement → cycle
  int cycleNode = -1;
  for (int[] e : edges)
    if (dist[e[0]] + e[2] < dist[e[1]]) {
      cycleNode = e[1];
      break;
    }
  return cycleNode != -1;
}

Tracing the cycle

Walk parent[] V times from cycleNode to reach a node on the cycle. Then trace parent V times more to get full cycle.

All-pairs check

Floyd-Warshall: diagonal < 0 for any vertex on a negative cycle. dp[i][i] < 0 → i on some negative cycle.

Applications

Arbitrage detection: currencies form graph, log(rate) as weight; negative cycle = profitable trade sequence.