In a directed graph where the edges may have positive or negative weights, the Bellman-Ford algorithm detects cycles in which the sum of weights is strictly negative ($<0$). I need to detect cycles in which the sum of weights is weakly negative ($\leq 0$). Here is my current idea:
- For each edge $e$, replace the weight $w_e$ with a vector of length 2, $(w_e.-1)$.
- Run Bellman-Ford on the graph with vector weights, where addition of vectors is done elementwise, the zero element is $(0,0)$, and comparison is done lexicographically.
Each strictly-negative cycle in the new graph has a weight of $(W,k)<(0,0)$, where either $W<0$, or $W=0$ and $k<0$. Since $k<0$ for every cycle, this amounts to $W\leq 0$, so in the original graph it is a weakly-negative cycle. Conversely, each weakly-negative cycle in the original graph has a weight of $W\leq 0$, so in the new graph it corresponds to a strictly-negative cycle.
Is this algorithm correct? Is the proof sufficiently accurate?