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