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?

  • 2
    $\begingroup$ Looks fine to me. It seems like a tidy equivalent to subtracting some tiny $\epsilon$ from every edge. $\endgroup$ – j_random_hacker Apr 16 '19 at 14:59
  • $\begingroup$ @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).. $\endgroup$ – Erel Segal-Halevi Apr 16 '19 at 17:33
  • $\begingroup$ Using weakly-negativity to indicate non-positive is not quite mathematical. $\endgroup$ – Thinh D. Nguyen Apr 17 '19 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.