Karp's Minimum Mean Cycle Algorithm

Karp's identity

μ* = min_v max_{k=0..V-1} (d_V(v) - d_k(v)) / (V - k). Where d_k(v) = shortest walk of length exactly k ending at v.

DP

// dp[k][v] = shortest walk of exactly k edges ending at v
dp[0][src] = 0, all else = INF
for k in 1..V
  for each edge (u, v, w)
    dp[k][v] = min(dp[k][v], dp[k-1][u] + w)
// Apply Karp's identity

Complexity

O(VE). Slow but definitive answer.

Applications

Amortized analysis. System stability. Min cost cycle in transaction network.