Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Out of curiosity: why did you not post this on Computer Science? It does not strike me as a research-level question per se. – Raphael Jan 5 at 14:43
up vote 8 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.