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.)
Efficient algorithm for finding directed cycle with smallest average weight
graph algorithms
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.