Efficient algorithm for finding directed cycle with smallest average weight

Question

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.)

Answer 1

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.