Minimum Mean Weight Cycle (Karp)

Minimum Mean Weight Cycle asks for the cycle in a directed weighted graph whose average edge weight is the smallest. Karp's algorithm finds it without ever enumerating cycles — just one dynamic-programming table and a tidy minimax formula.

The slow way first

The brute-force idea is to enumerate every cycle, sum its weights, divide by its length, and take the minimum. But a graph can have an exponential number of cycles, so listing them is hopeless for anything but a toy graph. We need a method that never looks at a cycle directly.

The question to ask: what stable quantity lets me reason about all cycles at once? The answer is the length of the shortest walk of exactly k edges to each vertex. That single table encodes enough to recover the best mean.

The idea: exactly-k shortest walks, then a minimax

Fix any source vertex. Let dp[k][v] be the least total weight of a walk from the source to v using exactly k edges. Build it for k = 0 up to k = n. Then Karp's theorem says the minimum mean cycle weight equals:

min over v of max over k < n of (dp[n][v] − dp[k][v]) / (n − k)

The inner max is the surprising part: for a fixed v we take the worst k, and only then minimize over vertices. That double extreme is exactly what pins down the cheapest average.

Walk through it

Step through the animation. We reveal the graph, then fill dp row by row: dp[0], dp[1], dp[2], dp[3]. Watch dp[3][B] = 7 appear. For v = B the best k is k = 1, giving (7 − 1) / (3 − 1) = 3 — exactly the mean of the cycle B → C → B.

Pseudocode

dp[0][v] = 0 for every vertex v        # any vertex may start a walk
for k = 1 .. n:
    for each edge (u, v, w):
        dp[k][v] = min(dp[k][v], dp[k-1][u] + w)
best = +infinity
for each vertex v with dp[n][v] finite:
    worst = max over k < n of (dp[n][v] - dp[k][v]) / (n - k)
    best = min(best, worst)
return best

The Python solution

def min_mean_cycle(n, edges):           # edges: (u, v, w)
    INF = float("inf")
    dp = [[INF] * n for _ in range(n + 1)]
    for v in range(n):
        dp[0][v] = 0                        # any vertex as a start
    for k in range(1, n + 1):
        for (u, v, w) in edges:
            if dp[k - 1][u] + w < dp[k][v]:
                dp[k][v] = dp[k - 1][u] + w
    best = INF
    for v in range(n):
        if dp[n][v] == INF:
            continue
        worst = max((dp[n][v] - dp[k][v]) / (n - k)
                    for k in range(n) if dp[k][v] < INF)
        best = min(best, worst)
    return best

• dp[0][v] = 0 for all v lets a walk begin at any vertex — essential so every cycle is reachable.
• The triple loop fills dp[k][v] = shortest walk of exactly k edges, relaxing every edge once per level.
• After the table is full, dp[n][v] is the row that the minimax compares against.
• For each v we take the max of (dp[n][v] − dp[k][v]) / (n − k) over all earlier k — the worst ratio.
• The outer min over vertices yields the minimum mean cycle weight.

Complexity

Filling the table is O(n · E) and the minimax pass is O(n²). The table itself dominates the space at O(n²). For dense graphs this is far better than touching cycles directly.

When this pattern shows up

Practice