基于线性规划的图最小费用流问题的消圈算法求解示例 我将为您讲解最小费用流问题的一个经典算法——消圈算法。这个算法基于一个直观原理：如果一个流是最小费用流，那么其残差网络中不存在负费用圈。 1. 问题描述 我们有一个有向图 \( G=(V, E) \)，其中每条边 \( e \in E \) 有两个参数： 容量 \( u_ e \ge 0 \)，表示该边允许通过的最大流量。 单位费用 \( c_ e \)，表示通过该边每单位流量所需的费用。 此外，图中每个顶点 \( v \in V \) 有一个 净需求 \( b(v) \)： 如果 \( b(v) > 0 \)，则 \( v \) 是“需求点”或“汇点”，需要接收 \( b(v) \) 单位的流量。 如果 \( b(v) < 0 \)，则 \( v \) 是“供应点”或“源点”，可以提供 \( -b(v) \) 单位的流量。 如果 \( b(v) = 0 \)，则是转运点。 我们要求一个 可行流 \( f: E \to \mathbb{R}_ {\ge 0} \)，满足： 容量约束 ：对所有边 \( e \)，有 \( 0 \le f(e) \le u_ e \)。 流量平衡约束 ：对每个顶点 \( v \)，流入量减去流出量等于其净需求。即： \[ \sum_ {(u, v) \in E} f(u, v) - \sum_ {(v, w) \in E} f(v, w) = b(v) \] 在满足以上条件的可行流中， 最小费用流问题 的目标是找到总费用最小的流，即最小化： \[ \sum_ {e \in E} c_ e f(e) \] 2. 解题过程：消圈算法 消圈算法的核心思想是 从任意一个可行流开始，不断在其残差网络中寻找负费用圈，然后沿这个圈增加流量，从而减少总费用，直到不存在负费用圈为止 。 步骤 0： 初始化 找到一个初始可行流 \( f \)。这可以通过求解一个只关心可行性（不关心费用）的最大流问题得到，或者如果问题结构简单（如单源单汇），可直接构造一个零流（如果满足平衡条件）。 步骤 1： 构造残差网络 \( G_ f \) 对于当前流 \( f \)，构造残差网络 \( G_ f = (V, E_ f) \)。 对于原图的每一条边 \( e = (u, v) \in E \)： 如果 \( f(e) < u_ e \)（即还有剩余容量），则在 \( G_ f \) 中加入一条 正向边 \( (u, v) \)，其 残差容量 为 \( r(u, v) = u_ e - f(e) \)， 残差费用 为 \( c'(u, v) = c_ e \)。 如果 \( f(e) > 0 \)（即已有流量可以退回），则在 \( G_ f \) 中加入一条 反向边 \( (v, u) \)，其 残差容量 为 \( r(v, u) = f(e) \)， 残差费用 为 \( c'(v, u) = -c_ e \)（因为退回流量相当于“赚回”原来的费用）。 步骤 2： 检测负费用圈 在残差网络 \( G_ f \) 中，寻找是否存在 总费用为负的圈 （简称“负圈”）。这可以通过Bellman-Ford算法或SPFA算法来实现，因为它们可以在有向图中检测负环。 如果 不存在 负费用圈，根据最小费用流的理论，当前的流 \( f \) 就是最小费用流。 算法结束 。 如果 存在 一个负费用圈 \( C \)，进入步骤3。 步骤 3： 沿圈增流 设找到的负费用圈为 \( C = (v_ 1, v_ 2, ..., v_ k, v_ 1) \)，其总费用 \( \sum_ {e \in C} c'(e) < 0 \)。 计算这个圈上每条边的 最大可调整流量 \( \delta \)： \[ \delta = \min_ {e \in C} \{ r(e) \} \] 其中 \( r(e) \) 是 \( G_ f \) 中边 \( e \) 的残差容量。 对这个圈 \( C \) 上的每条边进行调整： 如果 \( e \) 是 \( G_ f \) 中的正向边（对应原图的边 \( (u, v) \)），则将该边上的流量增加 \( \delta \)，即 \( f(u, v) := f(u, v) + \delta \)。 如果 \( e \) 是 \( G_ f \) 中的反向边（对应原图的边 \( (v, u) \)），则相当于将原边 \( (v, u) \) 上的流量减少 \( \delta \)，即 \( f(v, u) := f(v, u) - \delta \)。 由于是沿着一个圈增流，每个顶点的流入流出变化量相互抵消，因此流量平衡约束始终保持满足。容量约束也因 \( \delta \) 的定义而保持满足。 步骤 4： 更新流和费用 计算这次调整带来的 费用变化 ： \[ \Delta Cost = \delta \cdot \left( \sum_ {e \in C} c'(e) \right) \] 因为圈的总费用为负，所以 \( \Delta Cost < 0 \)，总费用严格下降。 更新总费用：\( TotalCost := TotalCost + \Delta Cost \)。 然后，返回到 步骤1 ，基于新的流 \( f \) 重新构造残差网络。 3. 算法正确性理解 关键定理 ：一个可行流是最小费用流， 当且仅当 它的残差网络中不存在负费用圈。 充分性（为什么没有负圈就是最优） ：如果存在另一个费用更低的可行流 \( f' \)，那么流之差 \( f' - f \) 可以表示为残差网络中一组圈流的叠加。由于 \( f' \) 的总费用更低，其中至少包含一个总费用为负的圈，这与假设矛盾。 必要性（为什么有负圈就可以改进） ：如果在 \( G_ f \) 中存在一个负费用圈，那么沿着这个圈发送一个正的流量 \( \delta \)，可以在保持流量平衡和容量约束的前提下，直接降低总费用。因此当前流 \( f \) 不是最优的。 4. 一个简单的计算示例 考虑一个简单的三角形图，帮助理解。 图结构 ： 顶点：\( V = \{1, 2, 3\} \) 边：\( E = \{(1,2), (2,3), (1,3)\} \) 参数：每条边的格式为 \( (容量， 单位费用) \) \( (1,2): (2, 1) \) \( (2,3): (1, 1) \) \( (1,3): (1, 3) \) 净需求：\( b(1) = -1 \) (供应1单位)， \( b(2) = 0 \)， \( b(3) = 1 \) (需求1单位)。 目标 ：找到从1到3的最小费用流，流量值为1。 算法执行过程 ： 初始化 ：从零流开始，\( f = 0 \)。零流可行吗？检查平衡：顶点1供应1单位，但零流无法送达顶点3，所以零流不可行。我们需要一个初始可行流。一个简单的方法是：从1直接送1单位到3，费用为3。所以初始可行流 \( f_ {12}=0, f_ {23}=0, f_ {13}=1 \)。总费用 = 3。 第一次迭代 ： 构造残差网络 \( G_ f \)： 边(1,2)：流量0，容量2，有正向边(1,2)，\( r=2, c'=1 \)。 边(2,3)：流量0，容量1，有正向边(2,3)，\( r=1, c'=1 \)。 边(1,3)：流量1，容量1。有反向边(3,1)，\( r=1, c'=-3 \)（因为退回流量节省费用）。 检测负圈：寻找圈。比如圈 \( 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \)。 费用 = \( c'(1,2) + c'(2,3) + c'(3,1) = 1 + 1 + (-3) = -1 < 0 \)。找到一个负费用圈！ 沿圈增流：圈上最小残差容量 \( \delta = min\{2, 1, 1\} = 1 \)。 沿(1,2)增加流量1：\( f_ {12} = 1 \)。 沿(2,3)增加流量1：\( f_ {23} = 1 \)。 沿(3,1)是反向边，意味着将原边(1,3)的流量减少1：\( f_ {13} = 0 \)。 更新后流：\( f_ {12}=1, f_ {23}=1, f_ {13}=0 \)。总费用变化 = \( 1 * (-1) = -1 \)，新总费用 = \( 3 - 1 = 2 \)。 第二次迭代 ： 构造新的残差网络 \( G_ f \)： 边(1,2)：流量1，容量2。有正向边(1,2)，\( r=1, c'=1 \)；有反向边(2,1)，\( r=1, c'=-1 \)。 边(2,3)：流量1，容量1。有反向边(3,2)，\( r=1, c'=-1 \)。 边(1,3)：流量0，容量1。有正向边(1,3)，\( r=1, c'=3 \)。 检测负圈：尝试找圈。例如，圈 \( 1 \rightarrow 2 \rightarrow 1 \) 的费用 = \( 1 + (-1) = 0 \)，非负。圈 \( 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \) 的费用 = \( 3 + 1 + (-1) = 3 > 0 \)。经检查， 不存在 总费用为负的圈。 算法终止 。 最终解 ：最小费用流为从1到2送1单位，从2到3送1单位。总费用为 \( 1 1 + 1 1 = 2 \)。这确实比初始方案（费用3）更优。 5. 算法特点与总结 优点 ： 概念清晰，直接基于“无负圈即最优”这一优美理论。 实现相对简单，只需能找负圈和更新流。 缺点 ： 最坏情况下的时间复杂度可能较差。如果每次只消除一个负圈且减少的费用很小，迭代次数可能非常多（伪多项式时间）。 严重依赖于初始可行流的质量。如果初始流费用很高，可能需要很多次消圈操作。 关联 ：消圈算法是许多更高效的最小费用流算法（如“最小平均圈消去法”、“代价缩放算法”）的理论基础。 此算法生动地展示了如何将优化问题（最小化总费用）转化为一个在残差网络中不断“纠错”（消除负圈）的过程。