最小成本流问题（Capacity Scaling Successive Shortest Path 算法）
字数 4074 2025-12-24 21:39:59

最小成本流问题（Capacity Scaling Successive Shortest Path 算法）

1. 问题描述

我们考虑一个带权有向图 \(G = (V, E)\)，其中每条边 \(e = (u, v) \in E\) 有：

  • 一个容量 \(c(e) \geq 0\)，表示该边最多能承载多少单位的“流”。
  • 一个单位成本 \(w(e)\)，表示每单位流经过该边时需要支付的成本。

此外，我们有一个目标流量值 \(F\)。问题的目标是：寻找一个从源点 \(s\) 到汇点 \(t\) 的流量，其大小恰好为 \(F\)，并且总运输成本最小。

更形式化地说，我们要为每条边分配一个流量 \(f(e)\)，满足：

  1. 容量约束：\(0 \leq f(e) \leq c(e)\)。
  2. 流量守恒：对于除了源点 \(s\) 和汇点 \(t\) 之外的每个顶点 \(v\)，流入 \(v\) 的总流量等于流出 \(v\) 的总流量。
  3. 流量需求：从 \(s\) 流出的净流量为 \(F\)，流入 \(t\) 的净流量也为 \(F\)。
  4. 目标函数：最小化总成本 \(\sum_{e \in E} w(e) \cdot f(e)\)。

2. 算法核心思想

最小成本流问题（Min-Cost Flow, MCF）有多种经典算法，如“连续最短路”（Successive Shortest Path, SSP）算法和“最小平均成本消圈”（Minimum Mean-Cycle Canceling）算法。我们今天要讲的是一种高效的容量缩放版本，全称为Capacity Scaling Successive Shortest Path 算法。

它的核心思想是分阶段贪心：

  • 我们不试图一次性满足最终流量 \(F\)，而是从一个较大的容量阈值 \(\Delta\) 开始，只考虑“剩余容量足够大（\(\geq \Delta\)）”的边，在当前这个“粗糙”的网络中，每次沿最短的增广路径（这里“最短”指的是路径的修正成本最短，即最小单位成本路径）推送尽可能多的流量，直到当前缩放尺度下无法再增加流量。
  • 然后将缩放尺度 \(\Delta\) 减半，考虑更多更“细”的边，重复上述过程，直到 \(\Delta < 1\)，此时算法终止，我们得到了一个流量为 \(F\) 且成本最小的流。

这种方法结合了“连续最短路”的正确性和“容量缩放”的效率，是实践中非常有效的最小成本流算法之一。

3. 基础工具：势函数与残量网络

在讲解具体步骤前，我们需要两个关键概念。

3.1 残量网络（Residual Graph）
对于当前的流量 \(f\)，我们为每条原图中的边 \(e = (u, v)\) 构建两条残量边：

  • 正向边：从 \(u\) 到 \(v\)，容量为 \(c(e) - f(e)\)（即剩余可用容量），成本为 \(w(e)\)。
  • 反向边：从 \(v\) 到 \(u\)，容量为 \(f(e)\)（表示可以撤回的流量），成本为 \(-w(e)\)。

残量网络 \(G_f\) 包含了所有这些残量边。在 \(G_f\) 中发送流量，等价于在原图中增加或减少对应边的流量。

3.2 势函数（Potentials）与修正成本
如果图中存在负成本的边，我们无法直接使用 Dijkstra 算法找最短路。为了解决这个问题，我们引入一个势函数 \(p: V \rightarrow \mathbb{R}\)。

对于残量网络中的一条边 \((u, v)\)，其修正成本（reduced cost）定义为：

\[w_p(u, v) = w(u, v) + p(u) - p(v) \]

一个关键性质是：在残量网络上沿着任何一条路径发送流量，其原始总成本的变化，等于其修正总成本的变化。因此，在修正成本下找到的最短路，对应着原始成本下的最短路。

更妙的是，如果我们能维护一组势 \(p\)，使得对于残量网络中的所有边，其修正成本都非负，即 \(w_p(u, v) \geq 0\)，那么我们就能在残量网络上安全地使用 Dijkstra 算法来寻找从 \(s\) 到任何点的最短（修正）路径了。

4. Capacity Scaling Successive Shortest Path 算法步骤

以下是算法的详细步骤。我们假设所有边的容量都是整数，目标流量 \(F\) 也是整数。

步骤 0：初始化

  • 令初始流量 \(f\) 为零流（所有边流量为0）。
  • 令初始势函数 \(p\) 为零向量（所有顶点势为0）。
  • 计算初始缩放尺度 \(\Delta = 2^{\lfloor \log_2 C \rfloor}\)，其中 \(C = \max_{(u,v) \in E} c(u, v)\)，即所有边容量的最大值的2的幂次上界。例如，若最大容量为13，则 \(\Delta = 16\)。

步骤 1：主循环（外循环，缩放阶段）
只要当前流量值小于目标 \(F\)，且 \(\Delta \geq 1\)，就重复以下步骤：

步骤 2：构建 \(\Delta\)-残量网络（\(\Delta\)-residual network）

  • 在当前的残量网络 \(G_f\) 中，我们只考虑那些剩余容量 \(r(u, v) \geq \Delta\) 的边。这个子图记为 \(G_f(\Delta)\)。
  • 注意，这些边的修正成本 \(w_p(u, v)\) 仍然保持非负（我们会维护这个性质）。

步骤 3：内循环（增广阶段）
在当前的 \(G_f(\Delta)\) 中，重复以下操作，直到无法从 \(s\) 到达 \(t\)，或者当前流量已达到 \(F\)：

  1. 寻找最短路：在 \(G_f(\Delta)\) 中，使用 Dijkstra 算法（因为修正成本非负），以修正成本 \(w_p\) 为边权，计算从源点 \(s\) 到所有其他顶点的最短路径距离（距离也是基于修正成本 \(w_p\)）。
  2. 检查可达性：如果汇点 \(t\) 不可达（距离为无穷大），则跳出内循环，进入步骤4（缩小 \(\Delta\)）。
  3. 更新势函数：令 \(dist_p(v)\) 为 Dijkstra 计算出的从 \(s\) 到 \(v\) 的最短（修正）距离。然后，我们按照以下规则更新势函数：

\[ p(v) := p(v) - dist_p(v) \]

这个更新是关键！**它能保证在新的势函数下，所有 $G_f$ 中的边的修正成本仍然保持非负**，并且从 $s$ 出发的所有最短路径上的边的修正成本变为0。这是算法能持续使用 Dijkstra 的基础。
  1. 增广：在（原始）残量网络 \(G_f\) 中，沿着从 \(s\) 到 \(t\) 的最短路（在修正成本为0的意义上），推送尽可能多的流量，但不超过该路径上所有边的最小剩余容量，同时也要确保推送后不超过目标总流量 \(F\)。推送的流量记为 \(augment\)。
  2. 更新流量：更新流量 \(f\) 和残量网络 \(G_f\)。

步骤 4：缩小缩放尺度

  • 当在当前的 \(G_f(\Delta)\) 中再也找不到从 \(s\) 到 \(t\) 的路径时，将缩放尺度减半：\(\Delta := \Delta / 2\)。
  • 然后回到步骤1，开始新的缩放阶段。

步骤 5：终止

  • 当总流量达到 \(F\) 时，算法成功终止，输出当前流 \(f\) 即为最小成本流。
  • 如果当 \(\Delta < 1\) 时流量仍未达到 \(F\)，说明不存在流量为 \(F\) 的可行流。

5. 为什么这样是对的？

  1. 可行性：算法始终在残量网络上推送流量，因此得到的流始终满足容量约束和流量守恒。
  2. 最优性（核心）：算法始终保持一个关键不变式：存在一组势 \(p\)，使得在当前的残量网络 \(G_f\) 中，所有边的修正成本 \(w_p(u, v) \geq 0\)。
    • 初始时，零流且 \(p=0\)，若原图无负环，则修正成本等于原始成本，非负。
    • 每次更新势 \(p(v) := p(v) - dist_p(v)\) 后，这个性质依然保持。这使得我们总能在 \(G_f\) 中找到一条从 \(s\) 到 \(t\) 的、修正成本为0的最短路。在修正成本下成本为0，意味着在原始成本下，这条路径的成本恰好等于路径终点势的差值。可以证明，每次沿着这样的零修正成本路径增广，不会引入负成本的增广环，因此最终得到的流在达到流量 \(F\) 时，其成本是最小的。
  3. 效率：容量缩放是关键。由于每次缩放阶段只考虑剩余容量大于等于 \(\Delta\) 的边，每次增广的流量至少为 \(\Delta\)。因此，每个缩放阶段内，增广次数是 \(O(m)\) 的（\(m\) 是边数）。由于 \(\Delta\) 从最大值按2的幂次减半到1，总共只有 \(O(\log C)\) 个缩放阶段。每个阶段内需要若干次 Dijkstra 操作。因此，总时间复杂度约为 \(O(m \log C \cdot (m + n \log n))\)。这比朴素的不带缩放的连续最短路算法（复杂度与流量值 \(F\) 有关）要高效得多，尤其是在容量和流量很大时。

6. 总结

Capacity Scaling Successive Shortest Path 算法是解决最小成本流问题的一个强大而实用的算法。它通过“容量缩放”将大问题分解为一系列在稀疏子图上求解的较小问题，并利用“势函数”来消除负边权，从而能够高效地使用 Dijkstra 算法寻找最小成本增广路径。这个算法清晰地展示了如何将网络流理论、最短路径算法和缩放技巧优雅地结合起来，解决一个经典的组合优化问题。

最小成本流问题（Capacity Scaling Successive Shortest Path 算法） 1. 问题描述 我们考虑一个 带权有向图 \(G = (V, E)\)，其中每条边 \(e = (u, v) \in E\) 有： 一个 容量 \(c(e) \geq 0\)，表示该边最多能承载多少单位的“流”。 一个 单位成本 \(w(e)\)，表示每单位流经过该边时需要支付的成本。 此外，我们有一个 目标流量值 \(F\)。问题的目标是：寻找一个从源点 \(s\) 到汇点 \(t\) 的 流量 ，其大小恰好为 \(F\)，并且总运输成本最小。 更形式化地说，我们要为每条边分配一个流量 \(f(e)\)，满足： 容量约束 ：\(0 \leq f(e) \leq c(e)\)。 流量守恒 ：对于除了源点 \(s\) 和汇点 \(t\) 之外的每个顶点 \(v\)，流入 \(v\) 的总流量等于流出 \(v\) 的总流量。 流量需求 ：从 \(s\) 流出的净流量为 \(F\)，流入 \(t\) 的净流量也为 \(F\)。 目标函数 ：最小化总成本 \(\sum_ {e \in E} w(e) \cdot f(e)\)。 2. 算法核心思想 最小成本流问题（Min-Cost Flow, MCF）有多种经典算法，如“连续最短路”（Successive Shortest Path, SSP）算法和“最小平均成本消圈”（Minimum Mean-Cycle Canceling）算法。我们今天要讲的是一种高效的 容量缩放版本 ，全称为 Capacity Scaling Successive Shortest Path 算法 。 它的核心思想是 分阶段贪心 ： 我们不试图一次性满足最终流量 \(F\)，而是从一个较大的容量阈值 \(\Delta\) 开始，只考虑“剩余容量足够大（\(\geq \Delta\)）”的边，在当前这个“粗糙”的网络中，每次沿 最短的增广路径 （这里“最短”指的是路径的 修正成本 最短，即最小单位成本路径）推送尽可能多的流量，直到当前缩放尺度下无法再增加流量。 然后将缩放尺度 \(\Delta\) 减半，考虑更多更“细”的边，重复上述过程，直到 \(\Delta < 1\)，此时算法终止，我们得到了一个流量为 \(F\) 且成本最小的流。 这种方法结合了“连续最短路”的正确性和“容量缩放”的效率，是实践中非常有效的最小成本流算法之一。 3. 基础工具：势函数与残量网络 在讲解具体步骤前，我们需要两个关键概念。 3.1 残量网络（Residual Graph） 对于当前的流量 \(f\)，我们为每条原图中的边 \(e = (u, v)\) 构建两条残量边： 正向边 ：从 \(u\) 到 \(v\)，容量为 \(c(e) - f(e)\)（即剩余可用容量），成本为 \(w(e)\)。 反向边 ：从 \(v\) 到 \(u\)，容量为 \(f(e)\)（表示可以撤回的流量），成本为 \(-w(e)\)。 残量网络 \(G_ f\) 包含了所有这些残量边。在 \(G_ f\) 中发送流量，等价于在原图中增加或减少对应边的流量。 3.2 势函数（Potentials）与修正成本 如果图中存在 负成本 的边，我们无法直接使用 Dijkstra 算法找最短路。为了解决这个问题，我们引入一个势函数 \(p: V \rightarrow \mathbb{R}\)。 对于残量网络中的一条边 \((u, v)\)，其 修正成本 （reduced cost）定义为： \[ w_ p(u, v) = w(u, v) + p(u) - p(v) \] 一个关键性质是： 在残量网络上沿着任何一条路径发送流量，其原始总成本的变化，等于其修正总成本的变化 。因此，在修正成本下找到的最短路，对应着原始成本下的最短路。 更妙的是，如果我们能维护一组势 \(p\)，使得 对于残量网络中的所有边，其修正成本都非负 ，即 \(w_ p(u, v) \geq 0\)，那么我们就能在残量网络上 安全地使用 Dijkstra 算法 来寻找从 \(s\) 到任何点的最短（修正）路径了。 4. Capacity Scaling Successive Shortest Path 算法步骤 以下是算法的详细步骤。我们假设所有边的容量都是整数，目标流量 \(F\) 也是整数。 步骤 0：初始化 令初始流量 \(f\) 为零流（所有边流量为0）。 令初始势函数 \(p\) 为零向量（所有顶点势为0）。 计算初始缩放尺度 \(\Delta = 2^{\lfloor \log_ 2 C \rfloor}\)，其中 \(C = \max_ {(u,v) \in E} c(u, v)\)，即所有边容量的最大值的2的幂次上界。例如，若最大容量为13，则 \(\Delta = 16\)。 步骤 1：主循环（外循环，缩放阶段） 只要当前流量值小于目标 \(F\)，且 \(\Delta \geq 1\)，就重复以下步骤： 步骤 2：构建 \(\Delta\)-残量网络（\(\Delta\)-residual network） 在当前的残量网络 \(G_ f\) 中，我们只考虑那些 剩余容量 \(r(u, v) \geq \Delta\) 的边。这个子图记为 \(G_ f(\Delta)\)。 注意，这些边的修正成本 \(w_ p(u, v)\) 仍然保持非负（我们会维护这个性质）。 步骤 3：内循环（增广阶段） 在当前的 \(G_ f(\Delta)\) 中，重复以下操作，直到无法从 \(s\) 到达 \(t\)，或者当前流量已达到 \(F\)： 寻找最短路 ：在 \(G_ f(\Delta)\) 中，使用 Dijkstra 算法 （因为修正成本非负），以修正成本 \(w_ p\) 为边权，计算从源点 \(s\) 到所有其他顶点的最短路径距离（距离也是基于修正成本 \(w_ p\)）。 检查可达性 ：如果汇点 \(t\) 不可达（距离为无穷大），则跳出内循环，进入步骤4（缩小 \(\Delta\)）。 更新势函数 ：令 \(dist_ p(v)\) 为 Dijkstra 计算出的从 \(s\) 到 \(v\) 的最短（修正）距离。然后，我们按照以下规则更新势函数： \[ p(v) := p(v) - dist_ p(v) \] 这个更新是关键！ 它能保证在新的势函数下，所有 \(G_ f\) 中的边的修正成本仍然保持非负 ，并且从 \(s\) 出发的所有最短路径上的边的修正成本变为0。这是算法能持续使用 Dijkstra 的基础。 增广 ：在（原始）残量网络 \(G_ f\) 中，沿着从 \(s\) 到 \(t\) 的最短路（在修正成本为0的意义上），推送尽可能多的流量，但不超过该路径上所有边的最小剩余容量，同时也要确保推送后不超过目标总流量 \(F\)。推送的流量记为 \(augment\)。 更新流量 ：更新流量 \(f\) 和残量网络 \(G_ f\)。 步骤 4：缩小缩放尺度 当在当前的 \(G_ f(\Delta)\) 中再也找不到从 \(s\) 到 \(t\) 的路径时，将缩放尺度减半：\(\Delta := \Delta / 2\)。 然后回到步骤1，开始新的缩放阶段。 步骤 5：终止 当总流量达到 \(F\) 时，算法成功终止，输出当前流 \(f\) 即为最小成本流。 如果当 \(\Delta < 1\) 时流量仍未达到 \(F\)，说明不存在流量为 \(F\) 的可行流。 5. 为什么这样是对的？ 可行性 ：算法始终在残量网络上推送流量，因此得到的流始终满足容量约束和流量守恒。 最优性（核心） ：算法始终保持一个关键不变式： 存在一组势 \(p\)，使得在当前的残量网络 \(G_ f\) 中，所有边的修正成本 \(w_ p(u, v) \geq 0\) 。 初始时，零流且 \(p=0\)，若原图无负环，则修正成本等于原始成本，非负。 每次更新势 \(p(v) := p(v) - dist_ p(v)\) 后，这个性质依然保持。这使得我们总能在 \(G_ f\) 中找到一条从 \(s\) 到 \(t\) 的、修正成本为0的最短路。在修正成本下成本为0，意味着在原始成本下，这条路径的成本恰好等于路径终点势的差值。可以证明， 每次沿着这样的零修正成本路径增广，不会引入负成本的增广环 ，因此最终得到的流在达到流量 \(F\) 时，其成本是最小的。 效率 ：容量缩放是关键。由于每次缩放阶段只考虑剩余容量大于等于 \(\Delta\) 的边，每次增广的流量至少为 \(\Delta\)。因此，每个缩放阶段内，增广次数是 \(O(m)\) 的（\(m\) 是边数）。由于 \(\Delta\) 从最大值按2的幂次减半到1，总共只有 \(O(\log C)\) 个缩放阶段。每个阶段内需要若干次 Dijkstra 操作。因此，总时间复杂度约为 \(O(m \log C \cdot (m + n \log n))\)。这比朴素的不带缩放的连续最短路算法（复杂度与流量值 \(F\) 有关）要高效得多，尤其是在容量和流量很大时。 6. 总结 Capacity Scaling Successive Shortest Path 算法是解决最小成本流问题的一个强大而实用的算法。它通过“容量缩放”将大问题分解为一系列在稀疏子图上求解的较小问题，并利用“势函数”来消除负边权，从而能够高效地使用 Dijkstra 算法寻找最小成本增广路径。这个算法清晰地展示了如何将 网络流理论、最短路径算法和缩放技巧 优雅地结合起来，解决一个经典的组合优化问题。