Skip to content
Tutorials Center
My learning

Topics

Lesson 137 of 225 ยท Shortest Paths and Spanning Trees

Minimum Mean Weight Cycle and Walks of Length k

Find the cycle with the smallest average edge weight using Karp's algorithm in Python, and count or minimise walks of exactly k edges with matrix powers over semirings.

Shortest-path lessons ask for the smallest total weight. Some problems ask for the smallest average instead. In a scheduling pipeline, a cycle of tasks that repeats forever has a long-run cost per step equal to the mean weight of its edges, and the cycle with the lowest mean decides how fast the system can run. This is the minimum mean weight cycle problem, and Karp's 1978 algorithm solves it in O(V E) time, with exactly the same shape as Bellman-Ford.

The second half of the lesson answers a different but related question: how many walks with exactly k edges are there between two vertices, and what is the cheapest one? Both are solved by raising a matrix to a power, only over different arithmetic.

Mean cycle weight

A cycle with edges of weights w1, ..., wL has mean (w1 + ... + wL) / L. A graph may have many cycles, and the one with the smallest total is not always the one with the smallest mean: a long cycle of small weights can beat a short cycle of tiny weights.

flowchart LR
    A((0)) -->|1| B((1))
    B -->|1| A
    B -->|"-1"| C((2))
    C -->|5| B
    C -->|"-2"| D((3))
    D -->|4| C

Three cycles: 0-1-0 has mean 1, 1-2-1 has mean 2, 2-3-2 has mean 1.

Karp's algorithm

Add a virtual source with 0-weight edges to every vertex (or simply start every vertex at distance 0). Let d[k][v] be the minimum weight of a walk with exactly k edges ending at v:

  • d[0][v] = 0 for every v.
  • d[k][v] = min over edges (u -> v) of d[k-1][u] + w(u, v).

This is Bellman-Ford without the early exit, with one row per pass. Karp's theorem says the minimum mean weight is

TEXT
mu* = min over v of  max over k in 0..n-1 of  (d[n][v] - d[k][v]) / (n - k)

where vertices with d[n][v] = infinity are skipped (no n-edge walk ends there). The intuition: a walk of n edges must repeat a vertex, so it contains a cycle, and comparing the n-edge walk with shorter walks to the same vertex exposes that cycle's average.

Python Karp's minimum mean cycle, checked by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the first graph the cycles 0-1-0 and 2-3-2 have means 1, and 1-2-1 has mean 2. Karp's answer is exactly 1, matching the brute-force search over every simple cycle. A DAG gives None because no walk of n edges exists. The second graph is built so that the best cycle 1-2-3-1 has total 4 over 3 edges, a fractional mean of 4/3, which is why we use Fraction instead of floats: exact arithmetic keeps ties exact.

Recovering the cycle

Karp returns only the number. To find an actual cycle, remember the predecessor of each d[k][v] entry, take the vertex v that achieves the minimum, and follow predecessors back from d[n][v]; the walk repeats a vertex and the repeated part is a cycle of mean mu*. An alternative is binary search on the answer: subtract a guess m from every weight and test with Bellman-Ford whether a negative cycle exists, because a negative cycle appears exactly when m exceeds the minimum mean.

Walks of exactly k edges

A walk may repeat vertices and edges (unlike a path). Let A be the adjacency matrix with A[i][j] = 1 if there is an edge i -> j. Then (A^k)[i][j] is the number of walks with exactly k edges from i to j, because multiplying by A extends every walk by one edge:

TEXT
(A^k)[i][j] = sum over m of (A^(k-1))[i][m] * A[m][j]

Change the arithmetic and you answer different questions with the same code. In the min-plus (tropical) semiring, "multiplication" becomes addition and "addition" becomes min:

TEXT
(W^k)[i][j] = min over m of (W^(k-1))[i][m] + W[m][j]

Now W^k[i][j] is the minimum weight of a walk with exactly k edges. Both multiplications are associative, so you can use fast exponentiation (square the matrix, as in fast exponentiation) and need only O(V^3 log k) time for any k, even 10^18 when counting modulo a prime.

Python Counting and minimising k-edge walks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four-edge walks from vertex 0 are counted in the first line, one entry per target vertex. The cheapest-walk lines show how the minimum can change with k: with a single edge you reach vertices 1 and 2 only, and as k grows, cycles through 3 -> 0 enter the picture. The last line confirms that repeated squaring gives the same matrix as k one-step products.

Which tool for which question?

Question Tool Time
Cheapest total weight, no repeats Dijkstra / Bellman-Ford O(E log V) / O(VE)
Smallest average cycle Karp O(VE)
Number of walks of length k matrix power over (+, x) O(V^3 log k)
Cheapest walk of exactly k edges min-plus matrix power O(V^3 log k)

Common mistakes

  • Using floats for means. Ties between cycles become wrong by rounding; use fractions or compare cross-multiplied integers.
  • Forgetting to skip d[n][v] = infinity. A vertex with no n-edge walk ending at it cannot be the minimiser.
  • Confusing "at most k" and "exactly k" edges. Min-plus powers give exactly k; add zero-weight self-loops (the identity trick) if you need "at most".
  • Overflow in counting. The number of walks grows exponentially; in other languages take results modulo a prime.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does d[k][v] mean in Karp's algorithm?

    Karp's table has one row per edge count and stores the cheapest walk of exactly that many edges ending at each vertex.
  2. 2. What is the running time of Karp's algorithm?

    It runs n rounds of Bellman-Ford-style relaxation over all E edges.
  3. 3. What does (A^k)[i][j] count when A is a 0/1 adjacency matrix?

    Each multiplication by A extends every walk by one edge, so the power counts walks of exactly k edges.
  4. 4. How do you get the cheapest walk with exactly k edges from a matrix power?

    The min-plus semiring replaces (+, x) with (min, +), so a matrix product extends walks and keeps the cheapest.

Summary

  • The minimum mean cycle minimises the average edge weight of a cycle, not its total.
  • Karp's algorithm fills d[k][v] for k = 0..n and returns min over v of max over k of (d[n][v] - d[k][v]) / (n - k) in O(V E).
  • Use exact fractions for the comparison; a DAG has no cycle and gives no answer.
  • Powers of the adjacency matrix count k-edge walks; the same powers over (min, +) give the cheapest k-edge walk.
  • Squaring makes any k cost O(V^3 log k).

Next: Counting Spanning Trees.