4
$\begingroup$

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

$\endgroup$
  • $\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 Jan 5 '16 at 14:43
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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