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$
$\endgroup$
-
$\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$ – Raphael Jan 5 '16 at 14:43
$\begingroup$
$\endgroup$
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.
