SPFA Cycle Detection

To detect negative cycles with SPFA, count how many times each node is relaxed. If any node is relaxed $n$ or more times, a negative cycle exists. Why?

Each relaxation extends the path by one edge. If a node needs $\geq n$ relaxations, the path uses $\geq n$ edges, implying a cycle. If the path keeps improving, the cycle is negative. This is simpler than running $n$ full iterations. You detect the cycle as soon as a node is relaxed $n$ times, which can happen early if the cycle is small.