xxx 最小费用最大流问题（Successive Shortest Path with Potentials 算法）
字数 2115 2025-11-08 10:02:46

xxx 最小费用最大流问题（Successive Shortest Path with Potentials 算法）

题目描述
给定一个带权有向图 \(G = (V, E)\)，每条边 \(e = (u, v)\) 有容量 \(c(e) \geq 0\) 和单位流量费用 \(w(e) \in \mathbb{R}\)。图中包含源点 \(s\) 和汇点 \(t\)。目标是找到从 \(s\) 到 \(t\) 的最大流 \(f\)，且总费用 \(\sum_{e} f(e) \cdot w(e)\) 最小。该问题称为最小费用最大流（Minimum Cost Maximum Flow, MCMF）。

解题过程

  1. 问题分析

    • 若仅需最大流，可用 Ford-Fulkerson 或 Dinic 算法。
    • 加入费用后，需在保证流最大的同时最小化总费用。直接枚举所有最大流不可行（计算量过大）。
    • 核心思路：在残量网络中寻找最短路径（按费用）来增量调整流，但需避免负权边导致的错误。

  2. 基础算法：Successive Shortest Path (SSP)

    • 步骤：
      1. 初始流 \(f = 0\)，残量网络 \(G_f\) 与原图相同。
      2. 在 \(G_f\) 中用 Bellman-Ford 算法找到从 \(s\) 到所有节点的最短路径（按费用 \(w\)）。
      3. 沿最短路径推送尽可能多的流（受路径上最小容量限制），更新 \(G_f\)。
      4. 重复步骤 2–3 直到无法增广（即 \(s\) 到 \(t\) 不连通）。
    • 问题：若存在负权边，每次需用 Bellman-Ford（复杂度 \(O(VE)\)），总复杂度 \(O(V E \cdot F)\)（\(F\) 为最大流值），效率低。

  3. 优化：引入势函数（Potentials）

    • 目标：避免负权边，使 Dijkstra 算法可替代 Bellman-Ford。
    • 关键思想：为每个节点 \(u\) 分配势 \(p(u)\)，将边 \((u, v)\) 的费用调整为 \(w_p(u, v) = w(u, v) + p(u) - p(v)\)。
    • 性质：调整后路径费用与原费用仅差 \(p(s) - p(t)\)，因此最短路径不变。
    • 势的更新：初始时通过 Bellman-Ford 计算 \(p(u)\)（即从 \(s\) 到 \(u\) 的最短距离），之后每次增广后更新势：

\[ p_{\text{new}}(u) = p(u) + d(u) \]

 其中 $ d(u) $ 是当前残量网络中用费用 $ w_p $ 求得的从 $ s $ 到 $ u $ 的最短距离（用 Dijkstra 计算）。

  1. 算法步骤（SSP with Potentials）

    • 输入：图 \(G = (V, E)\)，容量 \(c\)，费用 \(w\)，源点 \(s\)，汇点 \(t\)。
    • 输出：最大流 \(f\) 及最小费用。
    • 步骤：
      1. 初始化流 \(f = 0\)，势 \(p(u) = 0\)（若原图无负权边）；否则用 Bellman-Ford 计算初始 \(p(u)\)。
      2. 循环直到无法增广：
        a. 在残量网络 \(G_f\) 中，定义调整费用 \(w_p(u, v) = w(u, v) + p(u) - p(v)\)。
        b. 用 Dijkstra 算法找 \(s\) 到所有节点的最短路径（按 \(w_p\)），得到距离 \(d(u)\)。若 \(d(t) = \infty\)，终止。
        c. 沿 \(s \to t\) 的最短路径推送流 \(\delta = \min\{ c_f(e) \mid e \in \text{路径} \}\)，更新流 \(f\) 和残量网络。
        d. 更新势：\(p(u) \gets p(u) + d(u)\)（保证后续 \(w_p\) 非负）。
    • 复杂度：\(O(F \cdot (E \log V))\)（若用堆优化 Dijkstra），优于基础 SSP。

  2. 示例演示

    • 考虑简单图：边 \((s, a)\) 容量 2 费用 1；\((a, t)\) 容量 2 费用 2；\((s, t)\) 容量 1 费用 4。
    • 步骤：
      • 初始 \(p = 0\)，Dijkstra 找到路径 \(s \to a \to t\)（费用 3），流值 2，总费用 6。
      • 更新势后，\(w_p(s, t) = 4 + 0 - 3 = 1\)（仍可增广），推送流 1 经 \(s \to t\)，总费用 10。
    • 最终流值 3，费用最小。

总结
SSP with Potentials 通过势函数消除负权边，使 Dijkstra 可高效替代 Bellman-Ford，显著提升性能。该算法是求解最小费用最大流问题的标准方法之一。

xxx 最小费用最大流问题（Successive Shortest Path with Potentials 算法） 题目描述 给定一个带权有向图 \( G = (V, E) \)，每条边 \( e = (u, v) \) 有容量 \( c(e) \geq 0 \) 和单位流量费用 \( w(e) \in \mathbb{R} \)。图中包含源点 \( s \) 和汇点 \( t \)。目标是找到从 \( s \) 到 \( t \) 的最大流 \( f \)，且总费用 \( \sum_ {e} f(e) \cdot w(e) \) 最小。该问题称为 最小费用最大流 （Minimum Cost Maximum Flow, MCMF）。 解题过程 问题分析 若仅需最大流，可用 Ford-Fulkerson 或 Dinic 算法。 加入费用后，需在保证流最大的同时最小化总费用。直接枚举所有最大流不可行（计算量过大）。 核心思路： 在残量网络中寻找最短路径（按费用）来增量调整流 ，但需避免负权边导致的错误。 基础算法：Successive Shortest Path (SSP) 步骤： 初始流 \( f = 0 \)，残量网络 \( G_ f \) 与原图相同。 在 \( G_ f \) 中用 Bellman-Ford 算法找到从 \( s \) 到所有节点的最短路径（按费用 \( w \)）。 沿最短路径推送尽可能多的流（受路径上最小容量限制），更新 \( G_ f \)。 重复步骤 2–3 直到无法增广（即 \( s \) 到 \( t \) 不连通）。 问题：若存在负权边，每次需用 Bellman-Ford（复杂度 \( O(VE) \)），总复杂度 \( O(V E \cdot F) \)（\( F \) 为最大流值），效率低。 优化：引入势函数（Potentials） 目标 ：避免负权边，使 Dijkstra 算法可替代 Bellman-Ford。 关键思想 ：为每个节点 \( u \) 分配势 \( p(u) \)，将边 \( (u, v) \) 的费用调整为 \( w_ p(u, v) = w(u, v) + p(u) - p(v) \)。 性质 ：调整后路径费用与原费用仅差 \( p(s) - p(t) \)，因此最短路径不变。 势的更新 ：初始时通过 Bellman-Ford 计算 \( p(u) \)（即从 \( s \) 到 \( u \) 的最短距离），之后每次增广后更新势： \[ p_ {\text{new}}(u) = p(u) + d(u) \] 其中 \( d(u) \) 是当前残量网络中用费用 \( w_ p \) 求得的从 \( s \) 到 \( u \) 的最短距离（用 Dijkstra 计算）。 算法步骤（SSP with Potentials） 输入 ：图 \( G = (V, E) \)，容量 \( c \)，费用 \( w \)，源点 \( s \)，汇点 \( t \)。 输出 ：最大流 \( f \) 及最小费用。 步骤 ： 初始化流 \( f = 0 \)，势 \( p(u) = 0 \)（若原图无负权边）；否则用 Bellman-Ford 计算初始 \( p(u) \)。 循环直到无法增广： a. 在残量网络 \( G_ f \) 中，定义调整费用 \( w_ p(u, v) = w(u, v) + p(u) - p(v) \)。 b. 用 Dijkstra 算法找 \( s \) 到所有节点的最短路径（按 \( w_ p \)），得到距离 \( d(u) \)。若 \( d(t) = \infty \)，终止。 c. 沿 \( s \to t \) 的最短路径推送流 \( \delta = \min\{ c_ f(e) \mid e \in \text{路径} \} \)，更新流 \( f \) 和残量网络。 d. 更新势：\( p(u) \gets p(u) + d(u) \)（保证后续 \( w_ p \) 非负）。 复杂度 ：\( O(F \cdot (E \log V)) \)（若用堆优化 Dijkstra），优于基础 SSP。 示例演示 考虑简单图：边 \( (s, a) \) 容量 2 费用 1；\( (a, t) \) 容量 2 费用 2；\( (s, t) \) 容量 1 费用 4。 步骤： 初始 \( p = 0 \)，Dijkstra 找到路径 \( s \to a \to t \)（费用 3），流值 2，总费用 6。 更新势后，\( w_ p(s, t) = 4 + 0 - 3 = 1 \)（仍可增广），推送流 1 经 \( s \to t \)，总费用 10。 最终流值 3，费用最小。 总结 SSP with Potentials 通过势函数消除负权边，使 Dijkstra 可高效替代 Bellman-Ford，显著提升性能。该算法是求解最小费用最大流问题的标准方法之一。