最小平均费用环

形式陈述 ​

输入、输出和环的身份 ​

输入是有限有向多重图理路有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。，每条弧有独立 ID、起终点和精确有理费用（属于实数费用理路实数系Real number system · Ordered complete field满足序域公理与上确界完备性的数系。的可执行子类） $c_a$。允许平行弧、反平行弧和自环。对非空简单有向环 $C$，定义

自环的长度是一，两个不同身份的反向弧可构成长二环。若全图无有向环，返回“无环”，不把答案填成零。存在环时，输出 ${\mu }_{\ast }$、一条实际达到它的环，以及顶点势 $p$，使每条原弧满足

沿任意环相加时势抵消，右式证明它的均值至少为 ${\mu }_{\ast }$；输出环的均值恰好相等，又证明下界可达。这份证书只需逐弧加法和比较，不必重跑求解器。实数精确算术模型下定理相同，附件以有理数给出可执行接口。

恰好走 k 条弧 ​

先剔除没有任何入弧或出弧的孤立点，并保留内部下标与原顶点的对应。设剩下 $N$ 点。定义 $D_k(v)$ 为“可从任意顶点出发，恰好走 $k$ 条弧到达 $v$”的最小费用；不存在这种游走时为 $+\mathrm{\infty }$。于是

这里是动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。的分层状态：第 $k$ 行只读第 $k-1$ 行，没有“保留上一行值”的分支。加入那个分支求出的将是“至多 $k$ 条弧”，不能直接代入下面的公式。

Karp 的刻画在这个任意起点版本中写成

若所有 $D_N(v)$ 均无穷，图无环：长为 $N$ 的游走必重复顶点，而有环又能绕出任意长的游走。原文先在强连通分量中固定单源；任意起点初始化使各个分量一次参与，下面给出该版本的证明。[1，Theorem 1]

min–max 公式为什么成立 ​

先设 ${\mu }_{\ast }=0$。图中没有负环，任意起点到 $v$ 的最短费用 $d(v)$ 能由简单路达到，因此

对每个有限 $D_N(v)$，至少有一个 $k<N$ 达到 $d(v)$，相应差商非负；所以公式右边不小于零。

再取一个零费用环。从任意起点到该环上一点 $w$，选择达到 $d(w)$ 的简单路。接着反复绕零环，费用在每次回到 $w$ 时不变。这条长游走的每个前缀都必须是到其终点的最短游走：若某前缀可变便宜，接回余下部分便会使到 $w$ 的费用小于 $d(w)$。取长游走恰好第 $N$ 条弧的终点 $v$，得到 $D_N(v)=d(v)$。于是对所有有限 $D_k(v)$，差商都非正，而至少一个为零，内层最大值恰为零。

一般费用下，把每条弧费用减去 ${\mu }_{\ast }$。每个环均值减少 ${\mu }_{\ast }$，$D_k(v)$ 减少 $k{\mu }_{\ast }$，每个差商同样减少 ${\mu }_{\ast }$。移权后的最小均值为零，刚才的论证便给出原公式。

从均值恢复真正的环 ​

数值表求出 ${\mu }_{\ast }$ 后，令 $c_a^{\prime }=c_a-{\mu }_{\ast }$。所有环的 $c^{\prime }$ 费用非负，因此可从隐含的全点零费用虚拟源运行Bellman–Ford理路Bellman–Ford 算法Bellman–Ford algorithm通过反复松弛边求含负权边图的单源最短路并检测可达负环。，得到全图最短势 $p$。其三角不等式给出

在移权费用为零的最优环上，上述非负项的总和是零，因而每条弧都取等号。只保留等号成立的紧弧，再用深度优先搜索理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。找一条有向环，必能成功；该环的原费用就是 $|C|{\mu }_{\ast }$。DFS 使用灰色栈上的回边并记录实际弧 ID，可以原样处理自环和平行弧。

这样恢复时不需要断言“某个 DP 最优游走的任意重复片段就是答案”。DP 的终点和最大差商只决定数值，实际环另用可核验的紧弧条件筛出。