Karp Minimum Mean Cycle

Karp's algorithm identifies the minimum cycle mean of a directed, strongly connected graph. By maintaining a dynamic programming table of shortest walk distances of exact lengths, we can determine the cycle with the smallest average edge weight, which can also detect negative cycles.

Interactive Experiment

You can interactively explore the algorithm on different graphs using the module here. Follow these steps:

1. Select the Graph "Mixed" to see a more complex structure with varied weights.
2. Set the Edge offset to "0" initially.
3. Set the Vertex to "1" to focus on the bounds computed for vertex 1.
4. Set the Walk length to "3" to observe the full prefix walk cost. Note the DP costs and the "Minimum cycle mean".
5. Change the Edge offset to "-1". The minimum cycle mean will shift exactly by the offset, confirming the uniformity property.