<p>Karp has an algorithm that does exactly that. You can read about it in his paper <a href="http://www.sciencedirect.com/science/article/pii/0012365X78900110">"A characterization of the minimum cycle mean in a digraph."</a></p>

<p>There seem to be other algorithms proposed <a href="http://www.math.md/files/csjm/v6-n1/v6-n1-(pp27-34).pdf">here</a> which are perhaps easier to read.</p>

CC BY-SA 3.0
2016-01-05T12:54:58.677Z
2016-01-05T12:57:49.903Z
2016-01-05T12:57:49.903Z
Shaull
<p>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.)</p>

CC BY-SA 3.0
2016-01-05T14:43:01.497Z
Out of curiosity: why did you not post this on [cs.SE]? It does not strike me as a research-level question per se.
Raphael
<graph-algorithms>
Efficient algorithm for finding directed cycle with smallest average weight
user7823
# Efficient algorithm for finding directed cycle with smallest average weight

(Asked by: username_0 on 2016-01-05)

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

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: Out of curiosity: why did you not post this on [cs.SE]? It does not strike me as a research-level question per se.  

---

## 1 answers

### Answer by username_2 on 2016-01-05. Score: 8 | Accepted answer

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."](http://www.sciencedirect.com/science/article/pii/0012365X78900110)

There seem to be other algorithms proposed [here](http://www.math.md/files/csjm/v6-n1/v6-n1-(pp27-34).pdf) which are perhaps easier to read.


---

