xxx 最小费用最大流问题的 Successive Shortest Path with Potentials 算法 问题描述 给定一个有向图 G=(V,E)，其中每条边 e∈E 有容量 c(e)≥0 和费用 w(e)∈R。图中包含源点 s 和汇点 t。我们需要找到从 s 到 t 的最大流，并且在所有最大流中，总费用最小的那个流。 算法讲解 1. 问题理解与基本概念 首先，我们需要理解最小费用最大流问题的目标： 最大流：找到从 s 到 t 的最大流量值 最小费用：在所有能达到最大流的方案中，选择总运输费用最小的那个 每条边的费用 w(e) 表示单位流量通过该边所需的成本。总费用是所有边上流量与单位费用的乘积之和。 2. 残量图与负费用环 算法基于残量图的概念。对于原图中的每条边 (u,v)： 如果边上有流量 f(u,v)，在残量图中添加反向边 (v,u)，容量为 f(u,v)，费用为 -w(u,v) 剩余容量为 c(u,v) - f(u,v) 的正向边，费用为 w(u,v) 关键观察：如果残量图中存在负费用环，那么我们可以沿着这个环推送流量，在不改变总流量的情况下降低总费用。 3. 势函数与约化费用 为了高效检测最短路径，我们引入势函数 h: V→R。对于每条边 (u,v)，定义约化费用为： wₕ(u,v) = w(u,v) + h(u) - h(v) 势函数的选择要满足以下性质：对于残量图中的所有边，约化费用 wₕ(u,v) ≥ 0 4. 算法步骤 步骤1：初始化 设置初始流 f = 0（所有边上流量为0） 设置初始势函数 h = 0（所有顶点势值为0） 构建初始残量图 G_ f 步骤2：在残量图中寻找最短路径 使用约化费用 wₕ(u,v) 作为边权 在残量图 G_ f 中，从源点 s 到所有其他顶点运行 Bellman-Ford 算法（或 Dijkstra 算法，如果无负权） 得到从 s 到每个顶点 v 的最短距离 d(v) 步骤3：更新势函数 设置新的势函数：h(v) = h(v) + d(v)，对所有 v∈V 这个操作确保约化费用保持非负 步骤4：推送流量 在残量图中找到从 s 到 t 的最短路径 P（使用更新后的势函数） 计算路径 P 上的最小剩余容量：Δ = min{c_ f(u,v) | (u,v) ∈ P} 沿着路径 P 推送 Δ 单位的流量 更新残量图中的容量：正向边容量减少 Δ，反向边容量增加 Δ 步骤5：检查终止条件 如果无法从 s 到达 t（在残量图中），算法终止 否则，返回步骤2 5. 算法正确性分析 该算法正确性的关键在于： 势函数的更新保持了约化费用的非负性，使得后续可以使用更高效的 Dijkstra 算法 每次迭代都沿着当前的最小费用路径推送流量 当无法找到 s-t 路径时，说明已经达到最大流 由于每次都在当前残量图中选择最小费用路径，最终得到的是最小费用最大流 6. 复杂度分析 使用 Bellman-Ford 进行初始势函数计算：O(VE) 后续每次使用 Dijkstra 找最短路径：O(E + VlogV) 或 O(V²) 最多需要推送 F 次流量（F 是最大流值） 总复杂度：O(F·ElogV) 或 O(F·V²) 7. 实际应用考虑 在实际实现中，需要注意： 初始势函数计算可以使用一次 Bellman-Ford 算法 后续迭代中，由于约化费用非负，可以使用更高效的 Dijkstra 算法 对于大规模图，可以使用斐波那契堆优化 Dijkstra 算法 需要注意处理容量和费用的数值范围，避免溢出 这个算法结合了最大流算法和最短路径算法，通过势函数巧妙地处理了负权边问题，是解决最小费用最大流问题的经典方法。