6.7.1. Finding a Minimum Mean Cost Cycle

First, let us figure out how to find a minimum mean cost cycle. We break the algorithm for finding a minimum mean cost cycle into two parts. First we show that \(\mu^*_f\) can be computed in \(O(nm)\) time, again using a variation of the Bellman-Ford algorithm. Then we prove that we can find a cycle of mean cost \(\mu^*_f\) in \(O\bigl(n^2\bigr)\) additional time. Together, these two claims prove

Lemma 6.30: It takes \(O(nm)\) time to find a minimum mean cost cycle \(C\) in \(G^f\).