# Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length cycle, and no negative-length cycles?

Background information: The question came up when I tried to implement in code the solution to what is called the "tramp steamer" problem: Given a graph G(V,E) in which each node is associated with a cost $c_i$ and each edge is associated with a time (number of days) $t_i$, find the cycle with the smallest ratio of cost to time $\frac{\sum_i(c_i)}{\sum_i(t_i)}$ (i.e. minimal cost/day cycle).

One solution is to do a binary search with the range of possible rations, trying to identify the minimum cost-to-time ratio $\mu$. In each iteration of the binary search in the range $[left...right]$, you "guess" a value of $\mu = \frac{left+right}{2}$ and then run Bellman-Ford:

• if a negative cycle exists then the value of $\mu$ is too high; the range is reset to $[left...\mu]$
• if all cycles are positive then the value of $\mu$ is too low; the range is reset to $[\mu...right]$
• if there is a zero-length cycle (with all other cycles being positive), then we have found the best value for $\mu$ and we can stop, returning the zero-length cycle as the answer

How exactly is the third case detected? Assume the graph A->B->C->D->{A,B} with two cycles (fro D back to A or B) where the cycle B->C->D->B is the optimal one and yields zero length for some selection of $\mu$ for which the other cycle is positive. Suppose we happen to try this particular value of $\mu$ (let's assume it's during the very first iteration because we got lucky). If I am using vertex A as the fixed point from which I run Bellman-Ford on each iteration, it will complete successfully without detecting a negative cycle. But how would the zero-length cycle be identified?

Currently I only handle the first 2 cases and my implementation keeps iterating until the $[left...right]$ range becomes becomes too small, so that floating point precision can't handle a smaller range. At that point I detect that $\frac{left+right}{2}$ is equal to one of the range limits (either left or right) and stop the binary search. How would I go about detecting that a particular value of $\mu$ has produced a zero-length cycle?

Here's how you can detect whether a weighted graph $G$ contains a zero-length cycle, assuming it does not contain any negative cycle.

1. Run Bellman-Ford on it to compute the distance $d(v)$ from the source to $v$, for each vertex $v$.

2. Color each edge $(v,w)$ red if $d(v) + \text{wt}(v,w) = d(w)$.

3. Form a new unweighted, directed graph $G'$ containing just the red edges from $G$. Check whether $G'$ has any cycles, using a standard algorithm (e.g., depth-first search). This can be done in linear time.

I'll leave it to you as an exercise to prove that the original graph $G$ contains a zero-length cycle if and only if the new graph $G'$ has a cycle.

• what is the complexity of this algorithm? Apr 25, 2018 at 4:25
• @Turbo, you should be able to figure that out on your own. Try figuring out the complexity of each of hte 3 steps, separately.
– D.W.
Apr 25, 2018 at 15:47
• @D.W. How can you run Bellman-Ford, if you don't have a source vertex?
– Dani
Jan 26, 2021 at 9:38

Note that this answer only contains the proof that was left as an exercise by D.W.. First, give it a try by yourself. And, in case you get stuck then refer to it.

Statement: The original graph $$G$$ contains a zero-length cycle if and only if the new graph $$G′$$ has a cycle.

Proof: Let $$d_{s}(v)$$ denote the shortest path length from $$s$$ to $$v$$ for any $$v \in V$$. First, we will prove the "only if" direction.

$$(\to)$$ Suppose $$G$$ contains a zero weight cycle $$C = (u_{1},\dotsc,u_{k} )$$. For the sake of contradiction assume that $$G'$$ does not contain this cycle. It means there are some two vertices in $$C$$, say $$u_{1}$$ and $$u_{2}$$ for which $$d_{s}(u_{2}) \neq d_{s}(u_{1}) + w(u_{1},u_{2})$$. It means, $$d_{s}(u_{2}) < d_{s}(u_{1}) + w(u_{1},u_{2})$$. Let us call this equation $$(1)$$.

Now, consider the path $$p$$ from $$s$$ to $$u_{1}$$ as: $$s$$ -> $$u_{2}\dotsc$$->$$u_{k}$$->$$u_{1}$$. The length of this path is: $$(d_{s}(u_{2}) + length(u_{2} \textrm{ to } u_{1}))$$. Since $$length(u_{2} \textrm{ to } u_{1})+ w(u_{1},u_{2}) = 0$$. The length of $$p$$ is: $$(d_{s}(u_{2}) - w(u_{1},u_{2}))$$. From equation $$(1)$$, this value is at $$< d_{s}(u_{1})$$. It contradicts the fact that the shortest path length from $$s$$ to $$u_{1}$$ is $$d_{s}(u_{1})$$. This completes the proof of "only if" direction. Now, we will prove the other direction.

$$(\gets)$$ Suppose $$G'$$ has a cycle $$C = (u_{1},\dotsc,u_{k} )$$. We will show that the weight of this cycle is $$0$$.

Let $$u_{1}$$ and $$u_{2}$$ be the two vertices in $$C$$. We have that:

\begin{align} d_{s}(u_{1}) &= d_{s}(u_{k}) + w(u_{k},u_{1}) \\ &= d_{s}(u_{k-1}) + w(u_{k-1},u_{k}) + w(u_{k},u_{1})\\ &\quad ... continuing \\ &= d_{s}(u_{2}) + w(u_{2},u_{3}) + \dotsc + w(u_{k},u_{1}) \\ &= d_{s}(u_{1}) + w(u_{1},u_{2}) + w(u_{2},u_{3}) + \dotsc + w(u_{k},u_{1}) \\ &= d_{s}(u_{1}) + length(C)\\ \end{align}

It implies that the length of the cycle is $$0$$. This completes the proof of "if" direction.

Adding to the discussion, you can also detect negative or zero-length cycles using Floyd-Warshall in $$O(n^3)$$ by setting the initial value of the minimum distance of each node to itself as infinity.

Also, there is this problem (APIO 2017 Travelling Merchant) that is slightly similar to your problem, with a solution available here that also uses binary search and cycle detection.

I don't think there is a known algorithm to find whether there is a zero-distance cycle in a graph in a polynomial time, as it is an NP-complete problem.

As you might know, if a known NP-Complete problem $X$ can be reduced in polynomial time to another problem $Y$ ($X \leqslant_p Y$) then $Y$ is an NP-complete problem too. Such is the case with Zero-distance cycle problem (which I will call $Z$) and the Subset Sum Problem (which I will call $S$).

$S$ is a known NP-Complete problem. A proof of its NP-Completeness can be found in chapter 8, section 8.8 of Algorithm Design, by Jon Kleinberg and Éva Tardos. It reduces SAT to 3D-Matching to Subset-Sum. It has another version of $S$, but it can be proven equivalent by polynomial reduction with the one used in this answer.

Now, here's a proof of how $S \leqslant_p Z$:

Suppose you have an $S$ problem. Its input is a set $W = \{w_1, \ldots, w_n\} \subseteq \mathbb{Z}$. The input is accepted by $S$ if there is a subset $A \subseteq W$ so that

$$\sum_{a \in A} a = 0.$$

So let's model this $S$ problem as a $Z$ problem. To do so, we build a Graph $G = (V,E)$ with $2n$ vertices as follows:

• For each element $w_i$ we create two vertices, $u_i$ and $v_i$.
• For every $v_i$ we add the edge $(v_i,u_i)$ to $E$ with weight $w_i$.
• For every $u_i$ and $v_j$ we add the edge $(u_i, v_j)$ to $E$ with weight $0$.

For a three element $S$ problem we would get a graph such as this:

Now, we send that graph to an hypothetic $Z$ solver. Some important notes:

• If there is a cycle, it goes through at least one complete element ($u_i$ and $v_i$).
• If a cycle goes through such an element, the total distance increments by $w_i$.
• If a cycle goes through multiple elements, the total distance will be the sum of all of them.

As a conclusion, if a zero-distance cycle is found by the $Z$ solver, that would mean that there is a subset of $W$ with zero sum. This confirms that $S \leqslant_p Z$, and because of that $Z$ is NP-Complete.

• Your reduction seems wrong. Take for instance the set $\{-2,1\}$. In the graph you obtain, there is a 0-cycle which needs to take twice the value $1$, however there is no solution to the $S$-problem. Actually, testing the existence of a $0$-cycle in a directed graph (even in multiple dimensions) is known to be solvable in PTime. See (dl.acm.org/citation.cfm?id=62251).
– manu
Mar 23, 2018 at 14:49