Bellman-Ford and zero-distance cycle

ignougroup
Problem Detail: 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?

Asked By : Alexandros

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28897