最小费用流问题（Negative Cycle Canceling 算法）
字数 4739 2025-12-13 03:17:23

最小费用流问题（Negative Cycle Canceling 算法）

我将详细讲解最小费用流问题的一个经典精确算法：Negative Cycle Canceling (NCC) 算法。这个问题在运筹学、网络优化和资源分配中有广泛应用。

1. 问题描述

我们有一个带权有向图 G = (V, E)，其中：

  • 每个顶点 v ∈ V 有一个净供给量 b(v)：
    • 如果 b(v) > 0，表示 v 是供给点（源点）。
    • 如果 b(v) < 0，表示 v 是需求点（汇点）。
    • 如果 b(v) = 0，表示 v 是转运点。
    • 所有顶点的净供给总和必须满足 Σ b(v) = 0，即总供给等于总需求。
  • 每条边 (u, v) ∈ E 有两个属性：
    • 容量 c(u, v) ≥ 0：表示该边允许通过的最大流量。
    • 费用 a(u, v)：表示通过单位流量所需支付的费用（可以为负）。
  • 目标：找到一个流分配 f(u, v)，满足以下条件：
    1. 流量守恒：对于每个顶点 v，流入流量减去流出流量等于净供给 b(v)。
    2. 容量限制：0 ≤ f(u, v) ≤ c(u, v)。
    3. 总费用最小化：最小化 Σ [a(u, v) * f(u, v)]。

这个问题称为最小费用流问题。如果所有 b(v)=0，且我们指定一个源点 s 和一个汇点 t，并希望从 s 到 t 输送特定流量 F，则为最小费用最大流问题的一个子问题。

2. 算法核心思想

Negative Cycle Canceling 算法 基于一个深刻的优化理论原理：

  • 最优性条件：一个可行流 f 是最小费用流，当且仅当其残余网络中没有负费用的有向环（负权环）。
  • 残余网络：给定流 f，对于每条边 (u, v)：
    • 如果 f(u, v) < c(u, v)，则残余网络中有一条正向边 (u, v)，残余容量为 c(u, v) - f(u, v)，费用为 a(u, v)。
    • 如果 f(u, v) > 0，则残余网络中有一条反向边 (v, u)，残余容量为 f(u, v)，费用为 -a(u, v)。反向边表示可以撤销原有的流量。
  • 直观解释：如果在残余网络中存在一个负费用环，那么沿着这个环增加一个单位的循环流量（即在正向边上增流，反向边上减流），可以在保持流量守恒的前提下，降低总费用。因此，最优流中不应存在这样的“省钱机会”。

算法步骤如下：

  1. 找到初始可行流：忽略费用，只满足供给/需求和容量约束。
  2. 循环操作：在残余网络中寻找负费用环。如果找到，就沿着该环增流（尽可能多），以降低总费用。重复直到没有负费用环为止。

3. 算法步骤详解

步骤一：找到初始可行流

初始可行流可以不考虑费用，只要满足容量和流量守恒即可。常见方法：

  • 加入一个超级源点 S 和超级汇点 T：
    • 对每个 b(v) > 0 的点，从 S 到 v 连边，容量为 b(v)，费用为0。
    • 对每个 b(v) < 0 的点，从 v 到 T 连边，容量为 -b(v)，费用为0。
  • 原图的边保持不变。
  • 在新图上运行最大流算法（如Edmonds-Karp），从 S 到 T 求最大流。如果最大流值等于总供给量 Σ_{b(v)>0} b(v)，则原问题存在可行流，且该流即为一个初始可行流 f。
  • 另一种简单情况：如果所有 b(v)=0，那么零流（f=0）就是一个可行的初始流。

步骤二：构建残余网络

根据当前流 f，构建有向的残余网络 G_f = (V, E_f)：

  • 对原图的每条边 (u, v) ∈ E：
    • 如果 f(u, v) < c(u, v)，则 E_f 中加入边 (u, v)，容量 r(u, v) = c(u, v) - f(u, v)，费用 a_f(u, v) = a(u, v)。
    • 如果 f(u, v) > 0，则 E_f 中加入边 (v, u)，容量 r(v, u) = f(u, v)，费用 a_f(v, u) = -a(u, v)。
  • 残余网络中的边只存在于容量大于0的情况。

步骤三：检测负费用环

我们需要在 G_f 中检查是否存在总费用为负的有向环。这可以用Bellman-Ford 算法实现：

  • 令 dist[v] 表示从任意起点（例如顶点1）到 v 的最短路径估计值（按边费用 a_f 计算）。
  • 运行 |V|-1 轮松弛操作。
  • 再额外运行一轮松弛操作：如果任何一条边 (u, v) 满足 dist[u] + a_f(u, v) < dist[v]，则说明存在负环，并且顶点 v 在负环上或受负环影响。
  • 为了找出具体的负环，可以从 v 出发，通过前驱指针回溯，直到遇到重复顶点，就找到了一个环。

步骤四：消去负环

假设我们找到了一个负费用环 C。

  1. 计算环上所有边的瓶颈容量 Δ = min { r(u, v) | (u, v) ∈ C }。
  2. 对环上的每条边 (u, v)：
    • 如果 (u, v) 是原图的正向边，则增加流量：f(u, v) += Δ。
    • 如果 (u, v) 是原图的反向边（对应原边 (v, u)），则减少流量：f(v, u) -= Δ。
  3. 更新残余网络 G_f。
  4. 总费用减少量为 |a(C)| * Δ，其中 a(C) 是环的总费用（负数）。

步骤五：循环与终止

重复步骤二、三、四，直到残余网络 G_f 中再也检测不到负费用环。此时，根据最优性条件，当前流 f 就是最小费用流。

4. 实例演示

考虑一个简单例子，图有顶点 {1,2,3}，净供给 b(1)=2, b(2)=-1, b(3)=-1。

  • 边：(1→2): cap=5, cost=4； (1→3): cap=5, cost=2； (2→3): cap=5, cost=1。
    目标：满足供给/需求，最小化总费用。

初始可行流（忽略费用）：从1送1单位到2，送1单位到3。流 f(1,2)=1, f(1,3)=1，其他为0。总费用 = 41 + 21 = 6。

迭代1：构建残余网络。

  • 边 (1,2) 用了1，容量剩4，故残余正向边 (1,2): r=4, cost=4；同时有反向边 (2,1): r=1, cost=-4。
  • 类似，(1,3): r=4, cost=2；(3,1): r=1, cost=-2。
  • 边 (2,3) 未使用，故 (2,3): r=5, cost=1；无反向边。
    检测负环：找到环 2 → 3 → 1 → 2（费用：1 + (-2) + (-4) = -5 < 0）。瓶颈容量 Δ=1（三条边残余容量均≥1）。沿环增流：
  • (2,3) 是正向边，f(2,3)+=1。
  • (3,1) 对应原边 (1,3) 的反向边，所以 f(1,3)-=1（从1变0）。
  • (2,1) 对应原边 (1,2) 的反向边，所以 f(1,2)-=1（从1变0）。
    新流：f(1,2)=0, f(1,3)=0, f(2,3)=1。但流量守恒被破坏了吗？检查：
    顶点1：流出0，流入0，净供给应为2，现在为0 → 不满足。
    错误警示：这里演示时，我们疏忽了必须保持原图流量守恒。实际上，在消去负环时，我们只在残余网络的环上操作，不会破坏原图的流量守恒。让我们重新正确推导。

正确初始流：为满足 b(1)=2，我们可以设 f(1,2)=1, f(1,3)=1（如前）。现在残余网络 G_f 包含：

  • (1,2): r=4, cost=4；(2,1): r=1, cost=-4。
  • (1,3): r=4, cost=2；(3,1): r=1, cost=-2。
  • (2,3): r=5, cost=1。
    现在，环 2 → 3 → 1 → 2 在 G_f 中确实存在，因为：
    (2,3) 是 G_f 的正向边（来自原边 (2,3)，未使用），
    (3,1) 是 G_f 的反向边（对应原边 (1,3)，使用了1单位），
    (1,2) 不是从 1 到 2 在 G_f 中吗？等等，(1,2) 是 G_f 的正向边（来自原边 (1,2)，使用了1单位），但环需要从 2 到 1 的边，我们有 (2,1)（反向边）。所以环是 2 → 3 → 1 → 2？路径是：
    2 → 3 用边 (2,3)（存在），
    3 → 1 用边 (3,1)（存在，是反向边），
    1 → 2 用边 (1,2)（存在，是正向边）。
    对，这个环在 G_f 中存在，总费用 = 1 + (-2) + 4 = 3？等等，计算：
  • (2,3) 费用 = 1
  • (3,1) 费用 = -2
  • (1,2) 费用 = 4
    总和 = 3 > 0，不是负环。所以这个环不是负的。我之前的计算有误。

让我们系统性地找负环。用Bellman-Ford。假设起点为1，初始化 dist[1]=0, dist[2]=∞, dist[3]=∞。
松弛过程（略），未发现负环。所以初始流可能已经是最优？但我们凭直觉：从1到2费用4较贵，或许可以先用便宜路径 1→3 (cost2) 和 3→2 (若存在，但不存在)，但图没有 3→2 边，所以无法直接调整。实际上，这个简单例子中，初始流 1→2:1, 1→3:1 已经是最小费用，总费用6。因为没有其他方式在满足供需约束下重组流量。

为了展示负环消去，考虑另一个经典例子（最小费用流教材常见）：
顶点：1(供给2), 2(需求2)。边：1→2: cap=2, cost=3；1→2: cap=2, cost=5（平行边）。显然最优是全部用费用3的边，总费用6。如果初始流全用费用5的边，总费用10。残余网络包含反向边 (2,1): cost=-5 和正向边 (1,2): cost=3，形成环 1→2→1，费用=3+(-5)=-2<0，沿环增流1单位，就把一条费用5的边上的流量转移到费用3的边上，费用减少2。

5. 算法复杂度与优化

  • 每次找负环需要 O(|V|*|E|)（Bellman-Ford）。
  • 最多需要消去 O(|V|*|U|) 个负环，其中 U 是最大容量（若容量为整数）。在最坏情况下，复杂度是指数级的。但对于整数容量和费用，算法保证在有限步终止。
  • 实践中，该算法理论优美但效率不高，通常作为其他算法（如Successive Shortest Path 或 Primal-Dual）的理论基础。

6. 总结

  • 最小费用流问题是在满足供需约束和容量限制下，最小化总输送费用的优化问题。
  • Negative Cycle Canceling 算法 基于“最优流无负费用残余环”的原理。
  • 步骤：找初始可行流 → 构建残余网络 → 寻找负费用环 → 沿环增流以降低费用 → 重复至无负环。
  • 该算法是理解最小费用流优化原理的重要基础，但在实际中常用更高效的版本。

通过以上逐步分析，你应该能理解最小费用流问题的定义、NCC算法的原理和具体操作流程。

最小费用流问题（Negative Cycle Canceling 算法） 我将详细讲解 最小费用流问题 的一个经典精确算法： Negative Cycle Canceling (NCC) 算法 。这个问题在运筹学、网络优化和资源分配中有广泛应用。 1. 问题描述 我们有一个 带权有向图 G = (V, E) ，其中： 每个顶点 v ∈ V 有一个 净供给量 b(v) ： 如果 b(v) > 0 ，表示 v 是供给点（源点）。 如果 b(v) < 0 ，表示 v 是需求点（汇点）。 如果 b(v) = 0 ，表示 v 是转运点。 所有顶点的净供给总和必须满足 Σ b(v) = 0 ，即总供给等于总需求。 每条边 (u, v) ∈ E 有两个属性： 容量 c(u, v) ≥ 0 ：表示该边允许通过的最大流量。 费用 a(u, v) ：表示通过单位流量所需支付的费用（可以为负）。 目标 ：找到一个流分配 f(u, v) ，满足以下条件： 流量守恒 ：对于每个顶点 v ，流入流量减去流出流量等于净供给 b(v) 。 容量限制 ： 0 ≤ f(u, v) ≤ c(u, v) 。 总费用最小化 ：最小化 Σ [a(u, v) * f(u, v)] 。 这个问题称为 最小费用流问题 。如果所有 b(v)=0 ，且我们指定一个源点 s 和一个汇点 t ，并希望从 s 到 t 输送特定流量 F ，则为 最小费用最大流问题 的一个子问题。 2. 算法核心思想 Negative Cycle Canceling 算法 基于一个深刻的优化理论原理： 最优性条件 ：一个可行流 f 是最小费用流， 当且仅当 其残余网络中没有负费用的有向环（负权环）。 残余网络 ：给定流 f ，对于每条边 (u, v) ： 如果 f(u, v) < c(u, v) ，则残余网络中有一条正向边 (u, v) ，残余容量为 c(u, v) - f(u, v) ，费用为 a(u, v) 。 如果 f(u, v) > 0 ，则残余网络中有一条反向边 (v, u) ，残余容量为 f(u, v) ，费用为 -a(u, v) 。反向边表示可以撤销原有的流量。 直观解释 ：如果在残余网络中存在一个负费用环，那么沿着这个环增加一个单位的循环流量（即在正向边上增流，反向边上减流），可以在保持流量守恒的前提下， 降低总费用 。因此，最优流中不应存在这样的“省钱机会”。 算法步骤如下： 找到初始可行流 ：忽略费用，只满足供给/需求和容量约束。 循环操作 ：在残余网络中寻找负费用环。如果找到，就沿着该环增流（尽可能多），以降低总费用。重复直到没有负费用环为止。 3. 算法步骤详解 步骤一：找到初始可行流 初始可行流可以不考虑费用，只要满足容量和流量守恒即可。常见方法： 加入一个超级源点 S 和超级汇点 T ： 对每个 b(v) > 0 的点，从 S 到 v 连边，容量为 b(v) ，费用为0。 对每个 b(v) < 0 的点，从 v 到 T 连边，容量为 -b(v) ，费用为0。 原图的边保持不变。 在新图上运行 最大流算法 （如Edmonds-Karp），从 S 到 T 求最大流。如果最大流值等于总供给量 Σ_{b(v)>0} b(v) ，则原问题存在可行流，且该流即为一个初始可行流 f 。 另一种简单情况：如果所有 b(v)=0 ，那么零流（ f=0 ）就是一个可行的初始流。 步骤二：构建残余网络 根据当前流 f ，构建有向的残余网络 G_f = (V, E_f) ： 对原图的每条边 (u, v) ∈ E ： 如果 f(u, v) < c(u, v) ，则 E_f 中加入边 (u, v) ，容量 r(u, v) = c(u, v) - f(u, v) ，费用 a_f(u, v) = a(u, v) 。 如果 f(u, v) > 0 ，则 E_f 中加入边 (v, u) ，容量 r(v, u) = f(u, v) ，费用 a_f(v, u) = -a(u, v) 。 残余网络中的边只存在于容量大于0的情况。 步骤三：检测负费用环 我们需要在 G_f 中检查是否存在总费用为负的有向环。这可以用 Bellman-Ford 算法 实现： 令 dist[v] 表示从任意起点（例如顶点1）到 v 的最短路径估计值（按边费用 a_f 计算）。 运行 |V|-1 轮松弛操作。 再额外运行一轮松弛操作：如果任何一条边 (u, v) 满足 dist[u] + a_f(u, v) < dist[v] ，则说明存在负环，并且顶点 v 在负环上或受负环影响。 为了找出具体的负环，可以从 v 出发，通过前驱指针回溯，直到遇到重复顶点，就找到了一个环。 步骤四：消去负环 假设我们找到了一个负费用环 C 。 计算环上所有边的 瓶颈容量 Δ = min { r(u, v) | (u, v) ∈ C } 。 对环上的每条边 (u, v) ： 如果 (u, v) 是原图的 正向边 ，则增加流量： f(u, v) += Δ 。 如果 (u, v) 是原图的 反向边 （对应原边 (v, u) ），则减少流量： f(v, u) -= Δ 。 更新残余网络 G_f 。 总费用减少量为 |a(C)| * Δ ，其中 a(C) 是环的总费用（负数）。 步骤五：循环与终止 重复步骤二、三、四，直到残余网络 G_f 中再也检测不到负费用环。此时，根据最优性条件，当前流 f 就是最小费用流。 4. 实例演示 考虑一个简单例子，图有顶点 {1,2,3} ，净供给 b(1)=2, b(2)=-1, b(3)=-1 。 边： (1→2): cap=5, cost=4 ； (1→3): cap=5, cost=2 ； (2→3): cap=5, cost=1 。 目标：满足供给/需求，最小化总费用。 初始可行流 （忽略费用）：从1送1单位到2，送1单位到3。流 f(1,2)=1, f(1,3)=1 ，其他为0。总费用 = 4 1 + 2 1 = 6。 迭代1 ：构建残余网络。 边 (1,2) 用了1，容量剩4，故残余正向边 (1,2): r=4, cost=4 ；同时有反向边 (2,1): r=1, cost=-4 。 类似， (1,3): r=4, cost=2 ； (3,1): r=1, cost=-2 。 边 (2,3) 未使用，故 (2,3): r=5, cost=1 ；无反向边。 检测负环：找到环 2 → 3 → 1 → 2 （费用：1 + (-2) + (-4) = -5 < 0）。瓶颈容量 Δ=1（三条边残余容量均≥1）。沿环增流： (2,3) 是正向边， f(2,3)+=1 。 (3,1) 对应原边 (1,3) 的反向边，所以 f(1,3)-=1 （从1变0）。 (2,1) 对应原边 (1,2) 的反向边，所以 f(1,2)-=1 （从1变0）。 新流： f(1,2)=0, f(1,3)=0, f(2,3)=1 。但流量守恒被破坏了吗？检查： 顶点1：流出0，流入0，净供给应为2，现在为0 → 不满足。 错误警示 ：这里演示时，我们疏忽了必须保持 原图流量守恒 。实际上，在消去负环时，我们只在残余网络的环上操作， 不会破坏原图的流量守恒 。让我们重新正确推导。 正确初始流 ：为满足 b(1)=2 ，我们可以设 f(1,2)=1, f(1,3)=1 （如前）。现在残余网络 G_f 包含： (1,2): r=4, cost=4 ； (2,1): r=1, cost=-4 。 (1,3): r=4, cost=2 ； (3,1): r=1, cost=-2 。 (2,3): r=5, cost=1 。 现在，环 2 → 3 → 1 → 2 在 G_f 中确实存在，因为： (2,3) 是 G_f 的正向边（来自原边 (2,3) ，未使用）， (3,1) 是 G_f 的反向边（对应原边 (1,3) ，使用了1单位）， (1,2) 不是从 1 到 2 在 G_f 中吗？等等， (1,2) 是 G_f 的正向边（来自原边 (1,2) ，使用了1单位），但环需要从 2 到 1 的边，我们有 (2,1) （反向边）。所以环是 2 → 3 → 1 → 2 ？路径是： 2 → 3 用边 (2,3) （存在）， 3 → 1 用边 (3,1) （存在，是反向边）， 1 → 2 用边 (1,2) （存在，是正向边）。 对，这个环在 G_f 中存在，总费用 = 1 + (-2) + 4 = 3？等等，计算： (2,3) 费用 = 1 (3,1) 费用 = -2 (1,2) 费用 = 4 总和 = 3 > 0，不是负环。所以这个环不是负的。我之前的计算有误。 让我们系统性地找负环。用Bellman-Ford。假设起点为1，初始化 dist[1]=0, dist[2]=∞, dist[3]=∞ 。 松弛过程（略），未发现负环。所以初始流可能已经是最优？但我们凭直觉：从1到2费用4较贵，或许可以先用便宜路径 1→3 (cost2) 和 3→2 (若存在，但不存在) ，但图没有 3→2 边，所以无法直接调整。实际上，这个简单例子中，初始流 1→2:1, 1→3:1 已经是最小费用，总费用6。因为没有其他方式在满足供需约束下重组流量。 为了展示负环消去，考虑另一个经典例子（最小费用流教材常见）： 顶点：1(供给2), 2(需求2)。边： 1→2: cap=2, cost=3 ； 1→2: cap=2, cost=5 （平行边）。显然最优是全部用费用3的边，总费用6。如果初始流全用费用5的边，总费用10。残余网络包含反向边 (2,1): cost=-5 和正向边 (1,2): cost=3 ，形成环 1→2→1 ，费用=3+(-5)=-2 <0，沿环增流1单位，就把一条费用5的边上的流量转移到费用3的边上，费用减少2。 5. 算法复杂度与优化 每次找负环需要 O(|V|*|E|) （Bellman-Ford）。 最多需要消去 O(|V|*|U|) 个负环，其中 U 是最大容量（若容量为整数）。在最坏情况下，复杂度是指数级的。但对于整数容量和费用，算法保证在有限步终止。 实践中，该算法理论优美但效率不高，通常作为其他算法（如 Successive Shortest Path 或 Primal-Dual ）的理论基础。 6. 总结 最小费用流问题 是在满足供需约束和容量限制下，最小化总输送费用的优化问题。 Negative Cycle Canceling 算法 基于“最优流无负费用残余环”的原理。 步骤 ：找初始可行流 → 构建残余网络 → 寻找负费用环 → 沿环增流以降低费用 → 重复至无负环。 该算法是理解最小费用流优化原理的重要基础，但在实际中常用更高效的版本。 通过以上逐步分析，你应该能理解最小费用流问题的定义、NCC算法的原理和具体操作流程。