最小费用最大流问题的 Primal-Dual 算法
字数 2849 2025-12-22 12:14:13

最小费用最大流问题的 Primal-Dual 算法

题目描述

最小费用最大流（Minimum Cost Maximum Flow, MCMF）问题是网络流中的一个经典问题。给定一个有向图 \(G=(V, E)\)，每条边 \(e=(u, v)\) 有容量 \(c(e) \ge 0\) 和单位流量费用 \(w(e) \in \mathbb{R}\)。同时，图中有一个源点 \(s\) 和一个汇点 \(t\)。目标是从 \(s\) 到 \(t\) 输送尽可能大的流量，且在总流量最大的前提下，使输送流量的总费用最小。其中，总费用是每条边上的流量乘以该边的单位费用之和。

输入：有向图（包含边容量和费用）、源点 \(s\)、汇点 \(t\)。
输出：最大流量值以及达到该流量的最小总费用。

解题过程

最小费用最大流问题可以视为最大流问题的扩展，增加了费用最小化的目标。Primal-Dual 算法是解决该问题的一种常用高效方法，它结合了最短路径增广和对偶理论的思想。

1. 问题建模与线性规划形式

首先，将问题表述为线性规划：

  • 决策变量：对每条边 \(e\)，定义流量 \(f(e)\)。
  • 目标：最小化总费用 \(\sum_{e \in E} w(e) f(e)\)。
  • 约束：
    1. 容量约束：\(0 \le f(e) \le c(e)\)。
    2. 流量守恒：对每个非源汇节点 \(v\)，入流等于出流。
    3. 从 \(s\) 流出的总流量最大化（即达到最大流）。

线性规划的对偶问题会引入节点势能（potential）变量，这在 Primal-Dual 算法中起到关键作用。

2. 算法核心思想

Primal-Dual 算法的基本思路是在残量网络中反复寻找从 \(s\) 到 \(t\) 的最短增广路径（按费用作为边权），并沿该路径推送尽可能多的流量，直到无法再增广（达到最大流）。这里的“最短路径”是在考虑了节点势能调整后的残量网络上定义的，以确保每次找到的路径在当前残量网络中具有最小费用。

节点势能 \(p(v)\) 是一个实数，其作用是通过调整边的费用，使得所有边在调整后的费用非负，从而可以使用 Dijkstra 算法快速找到最短路径。

3. 算法步骤详解

假设初始时所有边流量为 0，节点势能 \(p(v) = 0\) 对所有 \(v \in V\)。算法迭代进行以下步骤，直到无法从 \(s\) 到 \(t\) 再找到增广路径：

步骤 1：构造调整费用（Reduced Cost）
对于残量网络中的每条边 \(e=(u, v)\)（包括反向边），其残量容量为 \(c_f(e)\)（原始容量减去当前流量），其调整费用定义为：

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

关键性质：如果 \(p\) 是最短路径距离的某种形式，那么 \(w_p(e) \ge 0\)，即调整费用非负。这使我们能用 Dijkstra 算法在 \(O((V+E)\log V)\) 时间内找到最短路径。

步骤 2：在调整费用非负的残量网络中找最短路径
在当前的残量网络上，以调整费用 \(w_p(e)\) 作为边权，使用 Dijkstra 算法计算从源点 \(s\) 到所有节点的最短路径距离 \(d(v)\)。如果 \(d(t) = +\infty\)，说明 \(t\) 不可达，已得到最大流，算法终止。

步骤 3：沿最短路径增广
从 \(s\) 到 \(t\) 的最短路径上，找出残量容量的最小值 \(\Delta = \min\{ c_f(e) : e \in \text{path} \}\)。
沿该路径推送 \(\Delta\) 的流量，更新残量网络（正向边减少残量容量，反向边增加）。

步骤 4：更新节点势能
增广后，更新节点势能以保持调整费用非负的性质：

\[p(v) \gets p(v) + d(v) \]

其中 \(d(v)\) 是步骤 2 中计算的最短距离。这个更新保证了下一轮迭代中，调整费用依然非负。

步骤 5：重复
回到步骤 1，继续下一轮增广。

4. 正确性说明

Primal-Dual 算法本质上是连续最短增广路算法（Successive Shortest Path）的扩展，通过势能函数保证每次能在非负权图中使用 Dijkstra 算法。其正确性基于线性规划的对偶理论：势能 \(p\) 对应着对偶变量，调整费用非负对应于互补松弛条件。每次迭代都在保持原始可行（流量可行）和对偶可行（调整费用非负）的前提下改进目标，直到达到最优。

5. 复杂度分析

  • 每次增广至少推送 1 单位流量（假设容量为整数），因此最多进行 \(F\) 次增广，其中 \(F\) 是最大流值。
  • 每次增广需要一次 Dijkstra 找最短路径，复杂度为 \(O((V+E)\log V)\)（使用优先队列）。
  • 总复杂度为 \(O(F \cdot (V+E)\log V)\)。在容量较大时可能较慢，但适用于许多实际问题。

6. 算法优化

实践中，如果边费用有负值，需要先用 Bellman-Ford 算法计算初始势能以消除负权边。此外，可以使用“势能重设”技巧，当势能过大时重新计算，避免数值问题。

7. 示例演示

考虑一个简单网络：顶点 \(\{s, a, b, t\}\)，边及（容量，费用）如下：

  • \(s \to a: (2, 1)\)
  • \(s \to b: (1, 3)\)
  • \(a \to b: (1, 1)\)
  • \(a \to t: (2, 2)\)
  • \(b \to t: (2, 1)\)
  1. 初始势能全 0，调整费用等于原费用。
  2. 第一轮：找 \(s\) 到 \(t\) 的最短路径（按费用）是 \(s \to a \to t\)（费用 1+2=3），推送 2 单位流量，更新残量网络，势能更新为各点最短距离 \(p(s)=0, p(a)=1, p(b)=3, p(t)=3\)。
  3. 第二轮：重新计算调整费用（例如边 \(a \to b\) 调整后费用为 \(1 + 1 - 3 = -1\)，但此时该边残量为 0 不在网络中，其他非负）。最短路径为 \(s \to b \to t\)（费用调整后为 0），推送 1 单位流量。
  4. 第三轮：找不到 \(s\) 到 \(t\) 的路径，停止。最大流量为 3，总费用计算为 \(2\times(1+2) + 1\times(3+1) = 6+4=10\)。

通过这个例子，你可以看到 Primal-Dual 算法如何逐步在保持费用最小的前提下增加流量，最终得到最小费用最大流。

最小费用最大流问题的 Primal-Dual 算法 题目描述 最小费用最大流（Minimum Cost Maximum Flow, MCMF）问题是网络流中的一个经典问题。给定一个有向图 \( G=(V, E) \)，每条边 \( e=(u, v) \) 有容量 \( c(e) \ge 0 \) 和单位流量费用 \( w(e) \in \mathbb{R} \)。同时，图中有一个源点 \( s \) 和一个汇点 \( t \)。目标是从 \( s \) 到 \( t \) 输送尽可能大的流量，且在总流量最大的前提下，使输送流量的总费用最小。其中，总费用是每条边上的流量乘以该边的单位费用之和。 输入 ：有向图（包含边容量和费用）、源点 \( s \)、汇点 \( t \)。 输出 ：最大流量值以及达到该流量的最小总费用。 解题过程 最小费用最大流问题可以视为最大流问题的扩展，增加了费用最小化的目标。Primal-Dual 算法是解决该问题的一种常用高效方法，它结合了最短路径增广和对偶理论的思想。 1. 问题建模与线性规划形式 首先，将问题表述为线性规划： 决策变量：对每条边 \( e \)，定义流量 \( f(e) \)。 目标：最小化总费用 \( \sum_ {e \in E} w(e) f(e) \)。 约束： 容量约束：\( 0 \le f(e) \le c(e) \)。 流量守恒：对每个非源汇节点 \( v \)，入流等于出流。 从 \( s \) 流出的总流量最大化（即达到最大流）。 线性规划的对偶问题会引入节点势能（potential）变量，这在 Primal-Dual 算法中起到关键作用。 2. 算法核心思想 Primal-Dual 算法的基本思路是在残量网络中反复寻找从 \( s \) 到 \( t \) 的 最短增广路径 （按费用作为边权），并沿该路径推送尽可能多的流量，直到无法再增广（达到最大流）。这里的“最短路径”是在考虑了节点势能调整后的残量网络上定义的，以确保每次找到的路径在当前残量网络中具有最小费用。 节点势能 \( p(v) \) 是一个实数，其作用是通过调整边的费用，使得所有边在调整后的费用非负，从而可以使用 Dijkstra 算法快速找到最短路径。 3. 算法步骤详解 假设初始时所有边流量为 0，节点势能 \( p(v) = 0 \) 对所有 \( v \in V \)。算法迭代进行以下步骤，直到无法从 \( s \) 到 \( t \) 再找到增广路径： 步骤 1：构造调整费用（Reduced Cost） 对于残量网络中的每条边 \( e=(u, v) \)（包括反向边），其残量容量为 \( c_ f(e) \)（原始容量减去当前流量），其调整费用定义为： \[ w_ p(e) = w(e) + p(u) - p(v) \] 关键性质：如果 \( p \) 是最短路径距离的某种形式，那么 \( w_ p(e) \ge 0 \)，即调整费用非负。这使我们能用 Dijkstra 算法在 \( O((V+E)\log V) \) 时间内找到最短路径。 步骤 2：在调整费用非负的残量网络中找最短路径 在当前的残量网络上，以调整费用 \( w_ p(e) \) 作为边权，使用 Dijkstra 算法计算从源点 \( s \) 到所有节点的最短路径距离 \( d(v) \)。如果 \( d(t) = +\infty \)，说明 \( t \) 不可达，已得到最大流，算法终止。 步骤 3：沿最短路径增广 从 \( s \) 到 \( t \) 的最短路径上，找出残量容量的最小值 \( \Delta = \min\{ c_ f(e) : e \in \text{path} \} \)。 沿该路径推送 \( \Delta \) 的流量，更新残量网络（正向边减少残量容量，反向边增加）。 步骤 4：更新节点势能 增广后，更新节点势能以保持调整费用非负的性质： \[ p(v) \gets p(v) + d(v) \] 其中 \( d(v) \) 是步骤 2 中计算的最短距离。这个更新保证了下一轮迭代中，调整费用依然非负。 步骤 5：重复 回到步骤 1，继续下一轮增广。 4. 正确性说明 Primal-Dual 算法本质上是连续最短增广路算法（Successive Shortest Path）的扩展，通过势能函数保证每次能在非负权图中使用 Dijkstra 算法。其正确性基于线性规划的对偶理论：势能 \( p \) 对应着对偶变量，调整费用非负对应于互补松弛条件。每次迭代都在保持原始可行（流量可行）和对偶可行（调整费用非负）的前提下改进目标，直到达到最优。 5. 复杂度分析 每次增广至少推送 1 单位流量（假设容量为整数），因此最多进行 \( F \) 次增广，其中 \( F \) 是最大流值。 每次增广需要一次 Dijkstra 找最短路径，复杂度为 \( O((V+E)\log V) \)（使用优先队列）。 总复杂度为 \( O(F \cdot (V+E)\log V) \)。在容量较大时可能较慢，但适用于许多实际问题。 6. 算法优化 实践中，如果边费用有负值，需要先用 Bellman-Ford 算法计算初始势能以消除负权边。此外，可以使用“势能重设”技巧，当势能过大时重新计算，避免数值问题。 7. 示例演示 考虑一个简单网络：顶点 \( \{s, a, b, t\} \)，边及（容量，费用）如下： \( s \to a: (2, 1) \) \( s \to b: (1, 3) \) \( a \to b: (1, 1) \) \( a \to t: (2, 2) \) \( b \to t: (2, 1) \) 初始势能全 0，调整费用等于原费用。 第一轮：找 \( s \) 到 \( t \) 的最短路径（按费用）是 \( s \to a \to t \)（费用 1+2=3），推送 2 单位流量，更新残量网络，势能更新为各点最短距离 \( p(s)=0, p(a)=1, p(b)=3, p(t)=3 \)。 第二轮：重新计算调整费用（例如边 \( a \to b \) 调整后费用为 \( 1 + 1 - 3 = -1 \)，但此时该边残量为 0 不在网络中，其他非负）。最短路径为 \( s \to b \to t \)（费用调整后为 0），推送 1 单位流量。 第三轮：找不到 \( s \) 到 \( t \) 的路径，停止。最大流量为 3，总费用计算为 \( 2\times(1+2) + 1\times(3+1) = 6+4=10 \)。 通过这个例子，你可以看到 Primal-Dual 算法如何逐步在保持费用最小的前提下增加流量，最终得到最小费用最大流。