Suppose we have a strongly connected directed graph with non-negative weights on its edges. Is there an efficient algorithm to find the directed cycle with the smallest average weight in the graph? (Here, smallest average weight of a directed cycle is the sum of the weights of all edges in the cycle divided by the number of edges.)
-
$\begingroup$ Out of curiosity: why did you not post this on Computer Science? It does not strike me as a research-level question per se. $\endgroup$– RaphaelJan 5, 2016 at 14:43
1 Answer
Karp has an algorithm that does exactly that. You can read about it in his paper "A characterization of the minimum cycle mean in a digraph."
There seem to be other algorithms proposed here which are perhaps easier to read.