# Finding weakly-negative cycles

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?

• Looks fine to me. It seems like a tidy equivalent to subtracting some tiny $\epsilon$ from every edge. – j_random_hacker Apr 16 '19 at 14:59
• @j_random_hacker indeed, the original idea was to subtract some $\epsilon$, but then this $\epsilon$ might affect the space requirements (if it is too tiny).. – Erel Segal-Halevi Apr 16 '19 at 17:33
• Using weakly-negativity to indicate non-positive is not quite mathematical. – Thinh D. Nguyen Apr 17 '19 at 5:55