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.)
1
-
$\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– Raphael2016-01-05 14:43:01 +00:00Commented Jan 5, 2016 at 14:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
