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?